Robotics & Artificial Intelligence Tools 2003 (Professional Edition)

home *** CD-ROM | disk | FTP | other *** search
/ Robotics & Artificial Int…3 (Professional Edition) / Robotics & Artificial Intelligence Tools 2003 (Professional Edition).iso / computer vision recognition / ratlib.src.tar < prev next >
Tape Archive | 2002-07-05 | 120.0 KB
open in:
MacOS 8.1 extracted |
Win98 extracted |
DOS extracted
view JSON data |
view as text

This file was processed as: Tape Archive (archive/tar).

You can browse this item here: ratlib.src.tar
Confidence	Program	Detection	Match Type	Support
`100%`	dexvert	Tape Archive `(archive/tar)`	magic	Supported
`100%`	file	POSIX tar archive	default
`99%`	file	POSIX tar archive, directory ratlib/, mode 000775 , uid 007207 , gid 000054 , size 00000000000 , seconds 06334350132, user jmcc, group pcvision	default
`98%`	file	data	default
`41%`	TrID	Sybase iAnywhere database files	default (weak)
`36%`	TrID	TAR - Tape ARchive (POSIX)	default
`21%`	TrID	TAR - Tape ARchive (directory)	default
`100%`	siegfried	x-fmt/265 Tape Archive Format	default
`100%`	lsar	Tar	default
`100%`	gt2	TAR Archiv gefunden (Auflistung ist deaktiviert)	default
`100%`	disktype	POSIX tar archive	default
`100%`	detectItEasy	Archive: tar	default
`100%`	binwalkID	POSIX tar archive	default
`100%`	xdgMime	application/x-tar	default
hex view
+--------+-------------------------+-------------------------+--------+--------+
|00000000| 72 61 74 6c 69 62 2f 00 | 00 00 00 00 00 00 00 00 |ratlib/.|........|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000050| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000060| 00 00 00 00 30 30 30 37 | 37 35 20 00 30 30 37 32 |....0007|75 .0072|
|00000070| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00000080| 30 30 30 30 30 30 30 20 | 30 36 33 33 34 33 35 30 |0000000 |06334350|
|00000090| 31 33 32 20 30 31 33 31 | 34 33 00 20 35 00 00 00 |132 0131|43. 5...|
|000000a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000000b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000000c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000000d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000000e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000000f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000100| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00000110| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000120| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00000130| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00000140| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00000150| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00000160| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000170| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000180| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000190| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000001a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000001b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000001c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000001d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000001e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000001f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000200| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 00 00 00 00 00 |ratlib/m|an/.....|
|00000210| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000220| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000230| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000240| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000250| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000260| 00 00 00 00 30 30 30 37 | 37 35 20 00 30 30 37 32 |....0007|75 .0072|
|00000270| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00000280| 30 30 30 30 30 30 30 20 | 30 35 37 36 31 31 34 34 |0000000 |05761144|
|00000290| 30 31 33 20 30 31 33 37 | 32 30 00 20 35 00 00 00 |013 0137|20. 5...|
|000002a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000002b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000002c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000002d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000002e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000002f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000300| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00000310| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000320| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00000330| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00000340| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00000350| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00000360| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000370| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000380| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000390| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000003a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000003b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000003c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000003d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000003e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000003f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000400| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00000410| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000420| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000430| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000440| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000450| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000460| 00 00 00 00 30 30 30 37 | 37 35 20 00 30 30 37 32 |....0007|75 .0072|
|00000470| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00000480| 30 30 30 30 30 30 30 20 | 30 35 37 36 31 33 36 32 |0000000 |05761362|
|00000490| 31 32 35 20 30 31 34 35 | 36 34 00 20 35 00 00 00 |125 0145|64. 5...|
|000004a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000004b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000004c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000004d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000004e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000004f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000500| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00000510| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000520| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00000530| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00000540| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00000550| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00000560| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000570| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000580| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000590| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000005f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000600| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00000610| 52 41 54 69 6e 74 72 6f | 2e 33 00 00 00 00 00 00 |RATintro|.3......|
|00000620| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000630| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000640| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000650| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000660| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00000670| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00000680| 30 30 30 37 33 35 31 20 | 30 35 37 36 31 31 37 30 |0007351 |05761170|
|00000690| 34 33 30 20 30 31 36 33 | 35 32 00 20 30 00 00 00 |430 0163|52. 0...|
|000006a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000006b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000006c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000006d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000006e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000006f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000700| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00000710| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000720| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00000730| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00000740| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00000750| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00000760| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000770| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000780| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000790| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000800| 2e 54 48 20 52 41 54 69 | 6e 74 72 6f 20 33 20 22 |.TH RATi|ntro 3 "|
|00000810| 32 35 20 4d 61 79 20 31 | 39 39 35 22 0a 2e 53 48 |25 May 1|995"..SH|
|00000820| 20 4e 41 4d 45 0a 69 6e | 74 72 6f 20 5c 2d 20 69 | NAME.in|tro \- i|
|00000830| 6e 74 72 6f 64 75 63 74 | 69 6f 6e 20 74 6f 20 52 |ntroduct|ion to R|
|00000840| 41 54 20 28 52 65 63 74 | 61 6e 67 6c 65 20 41 63 |AT (Rect|angle Ac|
|00000850| 63 65 73 73 20 54 72 65 | 65 29 20 6c 69 62 72 61 |cess Tre|e) libra|
|00000860| 72 79 20 66 75 6e 63 74 | 69 6f 6e 73 0a 2e 53 48 |ry funct|ions..SH|
|00000870| 20 53 59 4e 4f 50 53 49 | 53 0a 2e 42 20 23 69 6e | SYNOPSI|S..B #in|
|00000880| 63 6c 75 64 65 20 22 72 | 61 74 6c 69 62 2e 68 22 |clude "r|atlib.h"|
|00000890| 0a 2e 53 48 20 44 45 53 | 43 52 49 50 54 49 4f 4e |..SH DES|CRIPTION|
|000008a0| 0a 2e 49 58 20 69 6e 74 | 72 6f 64 75 63 74 69 6f |..IX int|roductio|
|000008b0| 6e 20 22 52 41 54 20 6c | 69 62 72 61 72 79 20 66 |n "RAT l|ibrary f|
|000008c0| 75 6e 63 74 69 6f 6e 73 | 22 0a 2e 49 58 20 22 52 |unctions|"..IX "R|
|000008d0| 41 54 20 6c 69 62 72 61 | 72 79 20 66 75 6e 63 74 |AT libra|ry funct|
|000008e0| 69 6f 6e 73 2c 20 69 6e | 74 72 6f 64 75 63 74 69 |ions, in|troducti|
|000008f0| 6f 6e 20 74 6f 22 0a 54 | 68 65 20 69 6e 63 6c 75 |on to".T|he inclu|
|00000900| 64 65 20 66 69 6c 65 0a | 2e 42 20 22 72 61 74 6c |de file.|.B "ratl|
|00000910| 69 62 2e 68 22 0a 63 6f | 6e 74 61 69 6e 73 20 64 |ib.h".co|ntains d|
|00000920| 65 63 6c 61 72 61 74 69 | 6f 6e 73 20 66 6f 72 20 |eclarati|ons for |
|00000930| 61 6c 6c 20 74 68 65 20 | 66 75 6e 63 74 69 6f 6e |all the |function|
|00000940| 73 20 61 6e 64 20 73 74 | 72 75 63 74 75 72 65 73 |s and st|ructures|
|00000950| 20 69 6d 70 6c 65 6d 65 | 6e 74 65 64 20 66 6f 72 | impleme|nted for|
|00000960| 20 75 73 65 0a 69 6e 20 | 74 68 65 20 52 41 54 20 | use.in |the RAT |
|00000970| 6c 69 62 72 61 72 79 2c | 0a 2e 42 52 20 6c 69 62 |library,|..BR lib|
|00000980| 72 61 74 20 2e 0a 43 20 | 70 72 6f 67 72 61 6d 73 |rat ..C |programs|
|00000990| 20 73 68 6f 75 6c 64 20 | 62 65 20 6c 69 6e 6b 65 | should |be linke|
|000009a0| 64 20 77 69 74 68 20 74 | 68 65 0a 2e 42 20 5c 2d |d with t|he..B \-|
|000009b0| 6c 72 61 74 0a 6f 70 74 | 69 6f 6e 20 69 6e 20 6f |lrat.opt|ion in o|
|000009c0| 72 64 65 72 20 74 6f 20 | 75 73 65 20 74 68 69 73 |rder to |use this|
|000009d0| 20 6c 69 62 72 61 72 79 | 2e 0a 2e 50 50 0a 54 68 | library|...PP.Th|
|000009e0| 69 73 20 6c 69 62 72 61 | 72 79 20 69 73 20 66 6f |is libra|ry is fo|
|000009f0| 72 20 69 6e 73 65 72 74 | 69 6e 67 2c 20 64 65 6c |r insert|ing, del|
|00000a00| 65 74 69 6e 67 2c 20 61 | 63 63 65 73 73 69 6e 67 |eting, a|ccessing|
|00000a10| 20 61 6e 64 20 71 75 65 | 72 79 69 6e 67 20 6f 62 | and que|rying ob|
|00000a20| 6a 65 63 74 73 20 77 68 | 69 63 68 0a 63 61 6e 20 |jects wh|ich.can |
|00000a30| 62 65 20 64 65 73 63 72 | 69 62 65 64 20 75 73 69 |be descr|ibed usi|
|00000a40| 6e 67 20 74 77 6f 20 64 | 69 6d 65 6e 73 69 6f 6e |ng two d|imension|
|00000a50| 61 6c 20 72 65 63 74 61 | 6e 67 75 6c 61 72 20 72 |al recta|ngular r|
|00000a60| 65 67 69 6f 6e 73 2e 20 | 20 41 73 73 6f 63 69 61 |egions. | Associa|
|00000a70| 74 65 64 20 77 69 74 68 | 0a 65 61 63 68 20 72 65 |ted with|.each re|
|00000a80| 63 74 61 6e 67 75 6c 61 | 72 20 6f 62 6a 65 63 74 |ctangula|r object|
|00000a90| 20 69 73 20 61 6e 20 61 | 72 62 69 74 72 61 72 79 | is an a|rbitrary|
|00000aa0| 0a 2e 42 20 28 76 6f 69 | 64 20 2a 29 0a 77 68 69 |..B (voi|d *).whi|
|00000ab0| 63 68 20 63 61 6e 20 62 | 65 20 75 73 65 64 20 74 |ch can b|e used t|
|00000ac0| 6f 20 68 6f 6c 64 0a 65 | 69 74 68 65 72 20 72 61 |o hold.e|ither ra|
|00000ad0| 77 20 64 61 74 61 20 6f | 72 20 61 20 70 6f 69 6e |w data o|r a poin|
|00000ae0| 74 65 72 20 74 6f 20 6f | 62 6a 65 63 74 20 64 61 |ter to o|bject da|
|00000af0| 74 61 2e 20 20 41 6c 6c | 20 72 65 63 74 61 6e 67 |ta.  All| rectang|
|00000b00| 75 6c 61 72 20 6f 62 6a | 65 63 74 73 20 61 72 65 |ular obj|ects are|
|00000b10| 0a 64 65 73 63 72 69 62 | 65 64 20 77 69 74 68 20 |.describ|ed with |
|00000b20| 66 6f 75 72 20 70 61 72 | 61 6d 65 74 65 72 73 2c |four par|ameters,|
|00000b30| 20 0a 2e 42 20 78 2c 0a | 2e 42 20 79 2c 0a 2e 42 | ..B x,.|.B y,..B|
|00000b40| 20 77 2c 0a 2e 42 20 68 | 2e 0a 2e 42 20 28 78 2c | w,..B h|...B (x,|
|00000b50| 79 29 0a 61 72 65 20 74 | 68 65 20 63 65 6e 74 65 |y).are t|he cente|
|00000b60| 72 20 70 6f 69 6e 74 20 | 6f 66 20 74 68 65 20 72 |r point |of the r|
|00000b70| 65 63 74 61 6e 67 6c 65 | 2c 20 61 6e 64 0a 2e 42 |ectangle|, and..B|
|00000b80| 20 28 77 2c 68 29 0a 61 | 72 65 20 74 68 65 20 77 | (w,h).a|re the w|
|00000b90| 69 64 74 68 20 61 6e 64 | 20 68 65 69 67 68 74 20 |idth and| height |
|00000ba0| 6f 66 20 74 68 65 20 72 | 65 63 74 61 6e 67 6c 65 |of the r|ectangle|
|00000bb0| 2c 20 6d 65 61 73 75 72 | 65 64 20 61 73 20 64 69 |, measur|ed as di|
|00000bc0| 73 74 61 6e 63 65 73 20 | 74 6f 20 74 68 65 20 65 |stances |to the e|
|00000bd0| 64 67 65 73 0a 66 72 6f | 6d 20 74 68 65 20 63 65 |dges.fro|m the ce|
|00000be0| 6e 74 65 72 2e 20 20 28 | 53 69 6d 69 6c 61 72 20 |nter.  (|Similar |
|00000bf0| 69 6e 20 6e 61 74 75 72 | 65 20 74 6f 20 74 68 65 |in natur|e to the|
|00000c00| 20 63 65 6e 74 65 72 20 | 61 6e 64 20 72 61 64 69 | center |and radi|
|00000c10| 69 20 6f 66 20 61 6e 20 | 65 6c 6c 69 70 73 65 2e |i of an |ellipse.|
|00000c20| 29 0a 54 68 65 20 71 75 | 65 72 69 65 73 20 73 75 |).The qu|eries su|
|00000c30| 70 70 6f 72 74 65 64 20 | 61 72 65 0a 72 65 63 74 |pported |are.rect|
|00000c40| 61 6e 67 6c 65 20 69 6e | 74 65 72 73 65 63 74 69 |angle in|tersecti|
|00000c50| 6f 6e 20 61 6e 64 20 63 | 6f 6e 74 61 69 6e 6d 65 |on and c|ontainme|
|00000c60| 6e 74 20 75 73 69 6e 67 | 20 61 6e 20 61 72 62 69 |nt using| an arbi|
|00000c70| 74 72 61 72 79 20 71 75 | 65 72 79 20 72 65 63 74 |trary qu|ery rect|
|00000c80| 61 6e 67 6c 65 2c 0a 61 | 6c 6f 6e 67 20 77 69 74 |angle,.a|long wit|
|00000c90| 68 20 61 6e 20 65 78 61 | 63 74 2f 63 6c 6f 73 65 |h an exa|ct/close|
|00000ca0| 20 6d 61 74 63 68 2e 0a | 2e 50 50 0a 54 68 65 20 | match..|.PP.The |
|00000cb0| 74 69 6d 65 20 6e 65 65 | 64 65 64 20 74 6f 20 69 |time nee|ded to i|
|00000cc0| 6e 73 65 72 74 2c 20 64 | 65 6c 65 74 65 20 61 6e |nsert, d|elete an|
|00000cd0| 64 20 61 63 63 65 73 73 | 20 69 6e 64 69 76 69 64 |d access| individ|
|00000ce0| 75 61 6c 20 70 6f 69 6e | 74 73 20 69 73 0a 61 6d |ual poin|ts is.am|
|00000cf0| 6f 72 74 69 7a 65 64 0a | 2e 42 20 4f 28 6c 6f 67 |ortized.|.B O(log|
|00000d00| 28 6e 29 29 20 2c 0a 61 | 6e 64 20 74 68 65 20 74 |(n)) ,.a|nd the t|
|00000d10| 69 6d 65 20 74 6f 20 70 | 65 72 66 6f 72 6d 20 65 |ime to p|erform e|
|00000d20| 69 74 68 65 72 20 71 75 | 65 72 79 20 69 73 0a 2e |ither qu|ery is..|
|00000d30| 66 74 20 42 0a 4f 28 6e | 5e 28 33 2f 34 29 20 2a |ft B.O(n|^(3/4) *|
|00000d40| 20 28 6c 6f 67 28 6e 29 | 20 5e 20 28 31 2f 34 29 | (log(n)| ^ (1/4)|
|00000d50| 29 20 2b 20 6b 29 0a 2e | 66 74 20 52 0a 77 68 65 |) + k)..|ft R.whe|
|00000d60| 72 65 0a 2e 42 20 6e 0a | 69 73 20 74 68 65 20 6e |re..B n.|is the n|
|00000d70| 75 6d 62 65 72 20 6f 66 | 20 72 65 63 74 61 6e 67 |umber of| rectang|
|00000d80| 6c 65 73 20 63 75 72 72 | 65 6e 74 6c 79 20 62 65 |les curr|ently be|
|00000d90| 69 6e 67 20 73 74 6f 72 | 65 64 20 61 6e 64 20 0a |ing stor|ed and .|
|00000da0| 2e 42 20 6b 0a 69 73 20 | 74 68 65 20 6e 75 6d 62 |.B k.is |the numb|
|00000db0| 65 72 20 6f 66 20 72 65 | 63 74 61 6e 67 6c 65 73 |er of re|ctangles|
|00000dc0| 20 77 68 69 63 68 20 6d | 61 74 63 68 20 74 68 65 | which m|atch the|
|00000dd0| 20 71 75 65 72 79 2e 0a | 2e 50 50 0a 2e 53 48 20 | query..|.PP..SH |
|00000de0| 44 41 54 41 20 53 54 52 | 55 43 54 55 52 45 53 0a |DATA STR|UCTURES.|
|00000df0| 54 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 73 74 |The foll|owing st|
|00000e00| 72 75 63 74 75 72 65 73 | 20 28 61 6e 64 20 74 79 |ructures| (and ty|
|00000e10| 70 65 64 65 66 27 73 29 | 20 61 72 65 20 64 65 66 |pedef's)| are def|
|00000e20| 69 6e 65 64 20 69 6e 20 | 74 68 65 0a 2e 42 20 22 |ined in |the..B "|
|00000e30| 72 61 74 6c 69 62 2e 68 | 22 0a 66 69 6c 65 3a 0a |ratlib.h|".file:.|
|00000e40| 2e 52 53 0a 2e 4c 50 0a | 2e 6e 66 0a 2e 66 74 20 |.RS..LP.|.nf..ft |
|00000e50| 42 0a 23 64 65 66 69 6e | 65 20 69 6e 74 33 32 20 |B.#defin|e int32 |
|00000e60| 69 6e 74 3b 20 20 20 20 | 20 20 20 20 20 20 20 20 |int;    |        |
|00000e70| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 4d |        |    /* M|
|00000e80| 61 63 68 69 6e 65 20 64 | 65 70 65 6e 64 65 6e 74 |achine d|ependent|
|00000e90| 20 2a 2f 0a 0a 74 79 70 | 65 64 65 66 20 69 6e 74 | */..typ|edef int|
|00000ea0| 33 32 20 52 41 54 56 65 | 63 74 6f 72 5b 34 5d 0a |32 RATVe|ctor[4].|
|00000eb0| 0a 74 79 70 65 64 65 66 | 20 73 74 72 75 63 74 20 |.typedef| struct |
|00000ec0| 5f 72 61 74 5f 6f 62 6a | 5f 6c 69 73 74 5f 20 7b |_rat_obj|_list_ {|
|00000ed0| 0a 09 76 6f 69 64 20 20 | 20 20 20 20 20 20 20 20 |..void  |        |
|00000ee0| 20 20 20 20 20 20 20 20 | 20 20 20 2a 6f 62 6a 65 |        |   *obje|
|00000ef0| 63 74 3b 0a 09 73 74 72 | 75 63 74 20 5f 72 61 74 |ct;..str|uct _rat|
|00000f00| 5f 6f 62 6a 5f 6c 69 73 | 74 5f 20 20 20 20 2a 6e |_obj_lis|t_    *n|
|00000f10| 65 78 74 3b 0a 7d 20 52 | 41 54 4f 62 6a 4c 69 73 |ext;.} R|ATObjLis|
|00000f20| 74 5f 74 2c 20 2a 52 41 | 54 4f 62 6a 4c 69 73 74 |t_t, *RA|TObjList|
|00000f30| 3b 0a 0a 74 79 70 65 64 | 65 66 20 73 74 72 75 63 |;..typed|ef struc|
|00000f40| 74 20 7b 0a 09 52 41 54 | 56 65 63 74 6f 72 20 20 |t {..RAT|Vector  |
|00000f50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6c |        |       l|
|00000f60| 6f 63 61 74 69 6f 6e 3b | 0a 09 52 41 54 4f 62 6a |ocation;|..RATObj|
|00000f70| 4c 69 73 74 5f 74 20 20 | 20 20 20 20 20 20 20 20 |List_t  |        |
|00000f80| 20 20 20 20 6f 62 6a 5f | 6c 69 73 74 3b 0a 7d 20 |    obj_|list;.} |
|00000f90| 2a 52 41 54 52 65 67 69 | 6f 6e 3b 0a 0a 74 79 70 |*RATRegi|on;..typ|
|00000fa0| 65 64 65 66 20 73 74 72 | 75 63 74 20 5f 72 61 74 |edef str|uct _rat|
|00000fb0| 5f 72 65 67 69 6f 6e 5f | 6c 69 73 74 5f 20 7b 0a |_region_|list_ {.|
|00000fc0| 09 52 41 54 52 65 67 69 | 6f 6e 20 20 20 20 20 20 |.RATRegi|on      |
|00000fd0| 20 20 20 20 20 20 20 20 | 20 20 20 72 65 67 69 6f |        |   regio|
|00000fe0| 6e 3b 0a 09 73 74 72 75 | 63 74 20 5f 72 61 74 5f |n;..stru|ct _rat_|
|00000ff0| 72 65 67 69 6f 6e 5f 6c | 69 73 74 5f 20 2a 6e 65 |region_l|ist_ *ne|
|00001000| 78 74 3b 0a 7d 20 52 41 | 54 52 65 67 69 6f 6e 4c |xt;.} RA|TRegionL|
|00001010| 69 73 74 5f 74 2c 20 2a | 52 41 54 52 65 67 69 6f |ist_t, *|RATRegio|
|00001020| 6e 4c 69 73 74 3b 0a 0a | 74 79 70 65 64 65 66 20 |nList;..|typedef |
|00001030| 73 74 72 75 63 74 20 7b | 0a 09 69 6e 74 20 28 2a |struct {|..int (*|
|00001040| 71 75 61 6c 69 66 69 65 | 72 29 28 76 6f 69 64 20 |qualifie|r)(void |
|00001050| 2a 71 75 61 6c 69 66 69 | 63 61 74 69 6f 6e 2c 20 |*qualifi|cation, |
|00001060| 76 6f 69 64 20 2a 6f 62 | 6a 29 3b 0a 09 76 6f 69 |void *ob|j);..voi|
|00001070| 64 20 2a 71 75 61 6c 69 | 66 69 63 61 74 69 6f 6e |d *quali|fication|
|00001080| 3b 0a 09 69 6e 74 20 28 | 2a 6f 70 65 72 61 74 69 |;..int (|*operati|
|00001090| 6f 6e 29 28 76 6f 69 64 | 20 2a 6f 70 65 72 61 6e |on)(void| *operan|
|000010a0| 64 2c 20 76 6f 69 64 20 | 2a 6f 62 6a 29 3b 0a 09 |d, void |*obj);..|
|000010b0| 76 6f 69 64 20 2a 6f 70 | 65 72 61 6e 64 3b 0a 7d |void *op|erand;.}|
|000010c0| 20 52 41 54 51 75 61 6c | 69 66 69 65 64 4f 70 65 | RATQual|ifiedOpe|
|000010d0| 72 61 74 69 6f 6e 3b 0a | 2e 66 74 20 52 0a 2e 66 |ration;.|.ft R..f|
|000010e0| 69 0a 2e 52 45 0a 2e 4c | 50 0a 2e 53 48 20 4c 49 |i..RE..L|P..SH LI|
|000010f0| 42 52 41 52 59 20 46 55 | 4e 43 54 49 4f 4e 53 0a |BRARY FU|NCTIONS.|
|00001100| 54 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 61 72 |The foll|owing ar|
|00001110| 65 20 74 68 65 20 66 75 | 6e 63 74 69 6f 6e 73 20 |e the fu|nctions |
|00001120| 74 68 61 74 20 61 72 65 | 20 64 65 66 69 6e 65 64 |that are| defined|
|00001130| 20 69 6e 20 74 68 65 20 | 0a 2e 42 20 72 61 74 6c | in the |..B ratl|
|00001140| 69 62 2e 68 0a 68 65 61 | 64 65 72 20 66 69 6c 65 |ib.h.hea|der file|
|00001150| 2e 20 20 0a 2e 42 20 52 | 41 54 43 6f 6d 70 75 74 |.  ..B R|ATComput|
|00001160| 65 54 72 61 6e 73 66 6f | 72 6d 0a 61 6e 64 20 0a |eTransfo|rm.and .|
|00001170| 2e 42 20 52 41 54 52 65 | 67 69 6f 6e 49 6e 76 65 |.B RATRe|gionInve|
|00001180| 72 74 0a 61 72 65 20 6d | 61 63 72 6f 73 2e 20 20 |rt.are m|acros.  |
|00001190| 49 66 20 0a 2e 42 20 52 | 41 54 5f 4e 4f 5f 49 4e |If ..B R|AT_NO_IN|
|000011a0| 4c 49 4e 45 0a 69 73 20 | 6e 6f 74 20 64 65 66 69 |LINE.is |not defi|
|000011b0| 6e 65 64 2c 20 74 68 65 | 20 66 6f 6c 6c 6f 77 69 |ned, the| followi|
|000011c0| 6e 67 20 61 72 65 20 61 | 6c 73 6f 20 6d 61 63 72 |ng are a|lso macr|
|000011d0| 6f 73 3a 0a 2e 42 20 52 | 41 54 4e 65 61 72 65 73 |os:..B R|ATNeares|
|000011e0| 74 4d 61 74 63 68 2c 20 | 52 41 54 49 6e 73 65 72 |tMatch, |RATInser|
|000011f0| 74 2c 0a 61 6e 64 20 0a | 2e 42 20 52 41 54 44 65 |t,.and .|.B RATDe|
|00001200| 6c 65 74 65 2e 0a 2e 4c | 50 0a 2e 6e 66 0a 2e 66 |lete...L|P..nf..f|
|00001210| 74 20 42 0a 52 41 54 43 | 6f 6d 70 75 74 65 54 72 |t B.RATC|omputeTr|
|00001220| 61 6e 73 66 6f 72 6d 28 | 76 65 63 2c 20 78 2c 20 |ansform(|vec, x, |
|00001230| 79 2c 20 77 2c 20 68 29 | 0a 09 52 41 54 56 65 63 |y, w, h)|..RATVec|
|00001240| 74 6f 72 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |tor     |        |
|00001250| 20 76 65 63 3b 0a 09 69 | 6e 74 33 32 20 20 20 20 | vec;..i|nt32    |
|00001260| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 78 2c |        |      x,|
|00001270| 20 79 2c 20 77 2c 20 68 | 3b 0a 0a 52 41 54 52 65 | y, w, h|;..RATRe|
|00001280| 67 69 6f 6e 49 6e 76 65 | 72 74 28 72 65 67 69 6f |gionInve|rt(regio|
|00001290| 6e 2c 20 78 2c 20 79 2c | 20 77 2c 20 68 29 0a 09 |n, x, y,| w, h)..|
|000012a0| 52 41 54 52 65 67 69 6f | 6e 20 20 20 20 20 20 20 |RATRegio|n       |
|000012b0| 20 20 20 20 20 20 20 72 | 65 67 69 6f 6e 3b 0a 09 |       r|egion;..|
|000012c0| 69 6e 74 33 32 20 20 20 | 20 20 20 20 20 20 20 20 |int32   |        |
|000012d0| 20 20 20 20 20 20 20 78 | 2c 20 79 2c 20 77 2c 20 |       x|, y, w, |
|000012e0| 68 3b 0a 0a 52 41 54 52 | 65 67 69 6f 6e 20 52 41 |h;..RATR|egion RA|
|000012f0| 54 43 72 65 61 74 65 52 | 65 67 69 6f 6e 28 78 2c |TCreateR|egion(x,|
|00001300| 20 79 2c 20 77 2c 20 68 | 2c 20 6f 62 6a 65 63 74 | y, w, h|, object|
|00001310| 29 0a 09 69 6e 74 33 32 | 20 20 20 20 20 20 20 20 |)..int32|        |
|00001320| 20 20 20 20 20 20 20 20 | 20 20 78 2c 20 79 2c 20 |        |  x, y, |
|00001330| 77 2c 20 68 3b 0a 09 76 | 6f 69 64 20 20 20 20 20 |w, h;..v|oid     |
|00001340| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2a 6f 62 |        |     *ob|
|00001350| 6a 65 63 74 3b 0a 0a 52 | 41 54 54 72 65 65 20 52 |ject;..R|ATTree R|
|00001360| 41 54 43 72 65 61 74 65 | 54 72 65 65 28 29 0a 0a |ATCreate|Tree()..|
|00001370| 52 41 54 52 65 67 69 6f | 6e 20 52 41 54 4e 65 61 |RATRegio|n RATNea|
|00001380| 72 65 73 74 4d 61 74 63 | 68 28 74 72 65 65 2c 20 |restMatc|h(tree, |
|00001390| 78 2c 20 79 2c 20 77 2c | 20 68 29 0a 09 52 41 54 |x, y, w,| h)..RAT|
|000013a0| 54 72 65 65 20 20 20 20 | 20 20 20 20 20 20 20 20 |Tree    |        |
|000013b0| 20 20 20 20 74 72 65 65 | 3b 0a 09 69 6e 74 33 32 |    tree|;..int32|
|000013c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000013d0| 20 20 78 2c 20 79 2c 20 | 77 2c 20 68 3b 0a 0a 76 |  x, y, |w, h;..v|
|000013e0| 6f 69 64 20 52 41 54 49 | 6e 73 65 72 74 28 74 72 |oid RATI|nsert(tr|
|000013f0| 65 65 2c 20 78 2c 20 79 | 2c 20 77 2c 20 68 2c 20 |ee, x, y|, w, h, |
|00001400| 6f 62 6a 65 63 74 29 0a | 09 52 41 54 54 72 65 65 |object).|.RATTree|
|00001410| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001420| 74 72 65 65 3b 0a 09 69 | 6e 74 33 32 20 20 20 20 |tree;..i|nt32    |
|00001430| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 78 2c |        |      x,|
|00001440| 20 79 2c 20 77 2c 20 68 | 3b 0a 09 76 6f 69 64 20 | y, w, h|;..void |
|00001450| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001460| 20 2a 6f 62 6a 65 63 74 | 3b 0a 0a 69 6e 74 20 52 | *object|;..int R|
|00001470| 41 54 44 65 6c 65 74 65 | 28 74 72 65 65 2c 20 78 |ATDelete|(tree, x|
|00001480| 2c 20 79 2c 20 77 2c 20 | 68 2c 20 6f 62 6a 65 63 |, y, w, |h, objec|
|00001490| 74 5f 6c 69 73 74 29 0a | 09 52 41 54 54 72 65 65 |t_list).|.RATTree|
|000014a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000014b0| 74 72 65 65 3b 0a 09 69 | 6e 74 33 32 20 20 20 20 |tree;..i|nt32    |
|000014c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 78 2c |        |      x,|
|000014d0| 20 79 2c 20 77 2c 20 68 | 3b 0a 09 52 41 54 4f 62 | y, w, h|;..RATOb|
|000014e0| 6a 4c 69 73 74 20 20 20 | 20 20 20 20 20 20 20 20 |jList   |        |
|000014f0| 20 20 6f 62 6a 65 63 74 | 5f 6c 69 73 74 3b 0a 0a |  object|_list;..|
|00001500| 52 41 54 52 65 67 69 6f | 6e 4c 69 73 74 20 52 41 |RATRegio|nList RA|
|00001510| 54 43 6f 6e 74 61 69 6e | 65 64 57 69 74 68 69 6e |TContain|edWithin|
|00001520| 28 74 72 65 65 2c 20 78 | 2c 20 79 2c 20 77 2c 20 |(tree, x|, y, w, |
|00001530| 68 29 0a 09 52 41 54 54 | 72 65 65 20 20 20 20 20 |h)..RATT|ree     |
|00001540| 20 20 20 20 20 20 20 20 | 20 20 20 74 72 65 65 3b |        |   tree;|
|00001550| 0a 09 69 6e 74 33 32 20 | 20 20 20 20 20 20 20 20 |..int32 |        |
|00001560| 20 20 20 20 20 20 20 20 | 20 78 2c 20 79 2c 20 77 |        | x, y, w|
|00001570| 2c 20 68 3b 0a 0a 52 41 | 54 52 65 67 69 6f 6e 4c |, h;..RA|TRegionL|
|00001580| 69 73 74 20 52 41 54 49 | 6e 74 65 72 73 65 63 74 |ist RATI|ntersect|
|00001590| 73 57 69 74 68 28 74 72 | 65 65 2c 20 78 2c 20 79 |sWith(tr|ee, x, y|
|000015a0| 2c 20 77 2c 20 68 29 0a | 09 52 41 54 54 72 65 65 |, w, h).|.RATTree|
|000015b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000015c0| 74 72 65 65 3b 0a 09 69 | 6e 74 33 32 20 20 20 20 |tree;..i|nt32    |
|000015d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 78 2c |        |      x,|
|000015e0| 20 79 2c 20 77 2c 20 68 | 3b 0a 0a 76 6f 69 64 20 | y, w, h|;..void |
|000015f0| 52 41 54 42 6f 75 6e 64 | 65 64 57 61 6c 6b 28 74 |RATBound|edWalk(t|
|00001600| 72 65 65 2c 20 62 6f 75 | 6e 64 73 2c 20 6f 70 65 |ree, bou|nds, ope|
|00001610| 72 61 74 69 6f 6e 29 0a | 09 52 41 54 54 72 65 65 |ration).|.RATTree|
|00001620| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001630| 74 72 65 65 3b 0a 09 52 | 41 54 52 65 67 69 6f 6e |tree;..R|ATRegion|
|00001640| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 62 6f |        |      bo|
|00001650| 75 6e 64 73 3b 0a 09 52 | 41 54 51 75 61 6c 69 66 |unds;..R|ATQualif|
|00001660| 69 65 64 4f 70 65 72 61 | 74 69 6f 6e 20 2a 6f 70 |iedOpera|tion *op|
|00001670| 65 72 61 74 69 6f 6e 3b | 0a 0a 76 6f 69 64 20 52 |eration;|..void R|
|00001680| 41 54 54 6f 74 61 6c 57 | 61 6c 6b 28 74 72 65 65 |ATTotalW|alk(tree|
|00001690| 2c 20 6f 70 65 72 61 74 | 69 6f 6e 29 0a 09 52 41 |, operat|ion)..RA|
|000016a0| 54 54 72 65 65 20 20 20 | 20 20 20 20 20 20 20 20 |TTree   |        |
|000016b0| 20 20 20 20 20 74 72 65 | 65 3b 0a 09 52 41 54 51 |     tre|e;..RATQ|
|000016c0| 75 61 6c 69 66 69 65 64 | 4f 70 65 72 61 74 69 6f |ualified|Operatio|
|000016d0| 6e 20 2a 6f 70 65 72 61 | 74 69 6f 6e 3b 0a 0a 2e |n *opera|tion;...|
|000016e0| 66 74 20 52 0a 2e 66 69 | 0a 00 00 00 00 00 00 00 |ft R..fi|........|
|000016f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001700| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001710| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001720| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001730| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001740| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001750| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001760| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001770| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001780| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001790| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000017a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000017b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000017c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000017d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000017e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000017f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001800| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00001810| 52 41 54 43 72 65 61 74 | 65 54 72 65 65 2e 33 00 |RATCreat|eTree.3.|
|00001820| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001830| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001840| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001850| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001860| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00001870| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00001880| 30 30 30 31 35 32 35 20 | 30 35 37 36 31 31 36 34 |0001525 |05761164|
|00001890| 35 36 37 20 30 31 37 32 | 35 35 00 20 30 00 00 00 |567 0172|55. 0...|
|000018a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000018b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000018c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000018d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000018e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000018f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001900| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00001910| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001920| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00001930| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00001940| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00001950| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00001960| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001970| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001980| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001990| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000019a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000019b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000019c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000019d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000019e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000019f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001a00| 2e 54 48 20 52 41 54 43 | 72 65 61 74 65 54 72 65 |.TH RATC|reateTre|
|00001a10| 65 20 33 20 22 32 35 20 | 4d 61 79 20 31 39 39 35 |e 3 "25 |May 1995|
|00001a20| 22 0a 2e 53 48 20 4e 41 | 4d 45 0a 52 41 54 43 72 |"..SH NA|ME.RATCr|
|00001a30| 65 61 74 65 54 72 65 65 | 20 5c 2d 20 43 72 65 61 |eateTree| \- Crea|
|00001a40| 74 65 20 61 20 52 65 63 | 74 61 6e 67 6c 65 20 41 |te a Rec|tangle A|
|00001a50| 63 63 65 73 73 20 54 72 | 65 65 20 73 74 72 75 63 |ccess Tr|ee struc|
|00001a60| 74 75 72 65 0a 2e 53 48 | 20 53 59 4e 4f 50 53 49 |ture..SH| SYNOPSI|
|00001a70| 53 0a 2e 4c 50 0a 2e 6e | 66 0a 2e 66 74 20 42 0a |S..LP..n|f..ft B.|
|00001a80| 23 69 6e 63 6c 75 64 65 | 20 22 72 61 74 6c 69 62 |#include| "ratlib|
|00001a90| 2e 68 22 0a 2e 66 69 0a | 2e 66 69 0a 2e 4c 50 0a |.h"..fi.|.fi..LP.|
|00001aa0| 2e 6e 66 0a 2e 66 74 20 | 42 0a 52 41 54 54 72 65 |.nf..ft |B.RATTre|
|00001ab0| 65 20 52 41 54 43 72 65 | 61 74 65 54 72 65 65 28 |e RATCre|ateTree(|
|00001ac0| 5c 7c 29 0a 2e 66 74 0a | 2e 66 69 0a 2e 49 58 20 |\|)..ft.|.fi..IX |
|00001ad0| 22 52 41 54 43 72 65 61 | 74 65 54 72 65 65 28 29 |"RATCrea|teTree()|
|00001ae0| 22 20 22 63 72 65 61 74 | 65 20 52 41 54 20 74 72 |" "creat|e RAT tr|
|00001af0| 65 65 22 0a 2e 53 48 20 | 44 45 53 43 52 49 50 54 |ee"..SH |DESCRIPT|
|00001b00| 49 4f 4e 0a 2e 4c 50 0a | 2e 42 20 52 41 54 43 72 |ION..LP.|.B RATCr|
|00001b10| 65 61 74 65 54 72 65 65 | 28 5c 7c 29 0a 63 72 65 |eateTree|(\|).cre|
|00001b20| 61 74 65 73 20 61 20 74 | 72 65 65 20 73 75 69 74 |ates a t|ree suit|
|00001b30| 61 62 6c 65 20 66 6f 72 | 20 75 73 65 20 69 6e 20 |able for| use in |
|00001b40| 74 68 65 20 52 41 54 20 | 6c 69 62 72 61 72 79 20 |the RAT |library |
|00001b50| 61 6e 64 20 72 65 74 75 | 72 6e 73 20 69 74 2e 20 |and retu|rns it. |
|00001b60| 20 49 74 20 63 61 6e 20 | 62 65 20 75 73 65 64 20 | It can |be used |
|00001b70| 66 6f 72 0a 64 79 6e 61 | 6d 69 63 61 6c 6c 79 20 |for.dyna|mically |
|00001b80| 69 6e 73 65 72 74 69 6e | 67 2c 20 64 65 6c 65 74 |insertin|g, delet|
|00001b90| 69 6e 67 2c 20 61 63 63 | 65 73 73 69 6e 67 20 61 |ing, acc|essing a|
|00001ba0| 6e 64 20 71 75 65 72 79 | 69 6e 67 20 6f 6e 20 72 |nd query|ing on r|
|00001bb0| 65 63 74 61 6e 67 75 6c | 61 72 0a 6f 62 6a 65 63 |ectangul|ar.objec|
|00001bc0| 74 73 2e 20 20 54 68 65 | 20 71 75 65 72 69 65 73 |ts.  The| queries|
|00001bd0| 20 77 68 69 63 68 20 63 | 61 6e 20 62 65 20 64 6f | which c|an be do|
|00001be0| 6e 65 20 61 72 65 20 72 | 65 63 74 61 6e 67 6c 65 |ne are r|ectangle|
|00001bf0| 20 69 6e 74 65 72 73 65 | 63 74 69 6f 6e 20 61 6e | interse|ction an|
|00001c00| 64 0a 63 6f 6e 74 61 69 | 6e 6d 65 6e 74 20 66 6f |d.contai|nment fo|
|00001c10| 72 20 61 72 62 69 74 72 | 61 72 79 20 71 75 65 72 |r arbitr|ary quer|
|00001c20| 79 20 72 65 63 74 61 6e | 67 6c 65 73 2e 20 20 41 |y rectan|gles.  A|
|00001c30| 73 73 6f 63 69 61 74 65 | 64 20 77 69 74 68 20 65 |ssociate|d with e|
|00001c40| 61 63 68 20 72 65 63 74 | 61 6e 67 6c 65 0a 69 73 |ach rect|angle.is|
|00001c50| 20 61 6e 20 61 72 62 69 | 74 72 61 72 79 20 6f 62 | an arbi|trary ob|
|00001c60| 6a 65 63 74 20 6f 66 20 | 74 79 70 65 0a 2e 42 20 |ject of |type..B |
|00001c70| 28 76 6f 69 64 20 2a 29 | 2c 0a 77 68 69 63 68 20 |(void *)|,.which |
|00001c80| 63 61 6e 20 62 65 20 75 | 73 65 64 20 74 6f 20 73 |can be u|sed to s|
|00001c90| 74 6f 72 65 20 61 20 70 | 6f 69 6e 74 65 72 20 74 |tore a p|ointer t|
|00001ca0| 6f 20 61 6e 20 6f 62 6a | 65 63 74 20 6f 72 20 61 |o an obj|ect or a|
|00001cb0| 73 20 74 68 65 20 61 63 | 74 75 61 6c 20 6f 62 6a |s the ac|tual obj|
|00001cc0| 65 63 74 0a 69 74 73 65 | 6c 66 2e 0a 2e 4c 50 0a |ect.itse|lf...LP.|
|00001cd0| 2e 53 48 20 53 45 45 20 | 41 4c 53 4f 0a 2e 42 52 |.SH SEE |ALSO..BR|
|00001ce0| 20 52 41 54 43 6f 6e 74 | 61 69 6e 65 64 57 69 74 | RATCont|ainedWit|
|00001cf0| 68 69 6e 20 28 33 29 2c | 0a 2e 42 52 20 52 41 54 |hin (3),|..BR RAT|
|00001d00| 44 65 6c 65 74 65 20 28 | 33 29 2c 0a 2e 42 52 20 |Delete (|3),..BR |
|00001d10| 52 41 54 49 6e 73 65 72 | 74 20 28 33 29 2c 0a 2e |RATInser|t (3),..|
|00001d20| 42 52 20 52 41 54 49 6e | 74 65 72 73 65 63 74 73 |BR RATIn|tersects|
|00001d30| 57 69 74 68 20 28 33 29 | 0a 2e 42 52 20 52 41 54 |With (3)|..BR RAT|
|00001d40| 4e 65 61 72 65 73 74 4d | 61 74 63 68 20 28 33 29 |NearestM|atch (3)|
|00001d50| 0a 2e 66 69 0a 65 20 74 | 68 65 20 63 65 6e 74 65 |..fi.e t|he cente|
|00001d60| 72 20 70 6f 69 6e 74 20 | 6f 66 20 74 68 65 20 72 |r point |of the r|
|00001d70| 65 63 74 61 6e 67 6c 65 | 2c 20 61 6e 64 0a 2e 42 |ectangle|, and..B|
|00001d80| 20 28 77 2c 68 29 0a 61 | 72 65 20 74 68 65 20 77 | (w,h).a|re the w|
|00001d90| 69 64 74 68 20 61 6e 64 | 20 68 65 69 67 68 74 20 |idth and| height |
|00001da0| 6f 66 20 74 68 65 20 72 | 65 63 74 61 6e 67 6c 65 |of the r|ectangle|
|00001db0| 2c 20 6d 65 61 73 75 72 | 65 64 20 61 73 20 64 69 |, measur|ed as di|
|00001dc0| 73 74 61 6e 63 65 73 20 | 74 6f 20 74 68 65 20 65 |stances |to the e|
|00001dd0| 64 67 65 73 0a 66 72 6f | 6d 20 74 68 65 20 63 65 |dges.fro|m the ce|
|00001de0| 6e 74 65 72 2e 20 20 28 | 53 69 6d 69 6c 61 72 20 |nter.  (|Similar |
|00001df0| 69 6e 20 6e 61 74 75 72 | 65 20 74 6f 20 74 68 65 |in natur|e to the|
|00001e00| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00001e10| 52 41 54 43 6f 6e 74 61 | 69 6e 65 64 57 69 74 68 |RATConta|inedWith|
|00001e20| 69 6e 2e 33 00 00 00 00 | 00 00 00 00 00 00 00 00 |in.3....|........|
|00001e30| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e40| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e50| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001e60| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00001e70| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00001e80| 30 30 30 33 33 33 33 20 | 30 35 37 36 31 33 35 36 |0003333 |05761356|
|00001e90| 34 31 37 20 30 32 30 33 | 31 35 00 20 30 00 00 00 |417 0203|15. 0...|
|00001ea0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001eb0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001ec0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001ed0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001ee0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001ef0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001f00| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00001f10| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001f20| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00001f30| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00001f40| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00001f50| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00001f60| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001f70| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001f80| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001f90| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001fa0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001fb0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001fc0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001fd0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001fe0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00001ff0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002000| 2e 54 48 20 52 41 54 43 | 6f 6e 74 61 69 6e 65 64 |.TH RATC|ontained|
|00002010| 57 69 74 68 69 6e 20 33 | 20 22 32 35 20 4d 61 79 |Within 3| "25 May|
|00002020| 20 31 39 39 35 22 0a 2e | 53 48 20 4e 41 4d 45 0a | 1995"..|SH NAME.|
|00002030| 52 41 54 43 6f 6e 74 61 | 69 6e 65 64 57 69 74 68 |RATConta|inedWith|
|00002040| 69 6e 20 5c 2d 20 47 69 | 76 65 6e 20 61 6e 20 61 |in \- Gi|ven an a|
|00002050| 72 62 69 74 72 61 72 79 | 20 72 65 63 74 61 6e 67 |rbitrary| rectang|
|00002060| 6c 65 20 61 6e 64 20 61 | 20 52 65 63 74 61 6e 67 |le and a| Rectang|
|00002070| 6c 65 20 41 63 63 65 73 | 73 20 54 72 65 65 2c 20 |le Acces|s Tree, |
|00002080| 66 69 6e 64 20 61 6c 6c | 20 72 65 63 74 61 6e 67 |find all| rectang|
|00002090| 6c 65 73 20 63 6f 6d 70 | 6c 65 74 65 6c 79 20 63 |les comp|letely c|
|000020a0| 6f 6e 74 61 69 6e 65 64 | 20 77 69 74 68 69 6e 20 |ontained| within |
|000020b0| 74 68 65 20 71 75 65 72 | 79 20 72 65 63 74 61 6e |the quer|y rectan|
|000020c0| 67 6c 65 2e 0a 2e 4c 50 | 0a 52 41 54 49 6e 74 65 |gle...LP|.RATInte|
|000020d0| 72 73 65 63 74 73 57 69 | 74 68 20 5c 2d 20 47 69 |rsectsWi|th \- Gi|
|000020e0| 76 65 6e 20 61 6e 20 61 | 72 62 69 74 72 61 72 79 |ven an a|rbitrary|
|000020f0| 20 72 65 63 74 61 6e 67 | 6c 65 20 61 6e 64 20 61 | rectang|le and a|
|00002100| 20 52 65 63 74 61 6e 67 | 6c 65 20 41 63 63 65 73 | Rectang|le Acces|
|00002110| 73 20 54 72 65 65 2c 20 | 66 69 6e 64 20 61 6c 6c |s Tree, |find all|
|00002120| 20 72 65 63 74 61 6e 67 | 6c 65 73 20 74 68 61 74 | rectang|les that|
|00002130| 20 69 6e 74 65 72 73 65 | 63 74 20 74 68 65 20 71 | interse|ct the q|
|00002140| 75 65 72 79 20 72 65 63 | 74 61 6e 67 6c 65 2e 0a |uery rec|tangle..|
|00002150| 2e 53 48 20 53 59 4e 4f | 50 53 49 53 0a 2e 4c 50 |.SH SYNO|PSIS..LP|
|00002160| 0a 2e 6e 66 0a 2e 66 74 | 20 42 0a 23 69 6e 63 6c |..nf..ft| B.#incl|
|00002170| 75 64 65 20 22 72 61 74 | 6c 69 62 2e 68 22 0a 2e |ude "rat|lib.h"..|
|00002180| 66 69 0a 2e 4c 50 0a 2e | 6e 66 0a 2e 66 74 20 42 |fi..LP..|nf..ft B|
|00002190| 0a 52 41 54 52 65 67 69 | 6f 6e 4c 69 73 74 20 52 |.RATRegi|onList R|
|000021a0| 41 54 43 6f 6e 74 61 69 | 6e 65 64 57 69 74 68 69 |ATContai|nedWithi|
|000021b0| 6e 28 74 72 65 65 2c 20 | 78 2c 20 79 2c 20 77 2c |n(tree, |x, y, w,|
|000021c0| 20 68 29 0a 09 52 41 54 | 54 72 65 65 20 74 72 65 | h)..RAT|Tree tre|
|000021d0| 65 3b 0a 09 69 6e 74 33 | 32 20 78 2c 20 79 2c 20 |e;..int3|2 x, y, |
|000021e0| 77 2c 20 68 3b 0a 0a 52 | 41 54 52 65 67 69 6f 6e |w, h;..R|ATRegion|
|000021f0| 4c 69 73 74 20 52 41 54 | 49 6e 74 65 72 73 65 63 |List RAT|Intersec|
|00002200| 74 73 57 69 74 68 28 74 | 72 65 65 2c 20 78 2c 20 |tsWith(t|ree, x, |
|00002210| 79 2c 20 77 2c 20 68 29 | 0a 09 52 41 54 54 72 65 |y, w, h)|..RATTre|
|00002220| 65 20 74 72 65 65 3b 0a | 09 69 6e 74 33 32 20 78 |e tree;.|.int32 x|
|00002230| 2c 20 79 2c 20 77 2c 20 | 68 3b 0a 2e 66 74 0a 2e |, y, w, |h;..ft..|
|00002240| 66 69 0a 2e 49 58 20 22 | 52 41 54 43 6f 6e 74 61 |fi..IX "|RATConta|
|00002250| 69 6e 65 64 57 69 74 68 | 69 6e 28 29 22 20 22 71 |inedWith|in()" "q|
|00002260| 75 65 72 79 20 52 41 54 | 22 0a 2e 49 58 20 22 52 |uery RAT|"..IX "R|
|00002270| 41 54 49 6e 74 65 72 73 | 65 63 74 73 57 69 74 68 |ATInters|ectsWith|
|00002280| 28 29 22 20 22 71 75 65 | 72 79 20 52 41 54 22 0a |()" "que|ry RAT".|
|00002290| 2e 53 48 20 44 45 53 43 | 52 49 50 54 49 4f 4e 0a |.SH DESC|RIPTION.|
|000022a0| 2e 4c 50 0a 2e 42 20 52 | 41 54 43 6f 6e 74 61 69 |.LP..B R|ATContai|
|000022b0| 6e 65 64 57 69 74 68 69 | 6e 28 5c 7c 29 0a 61 6e |nedWithi|n(\|).an|
|000022c0| 64 0a 2e 42 20 52 41 54 | 49 6e 74 65 72 73 65 63 |d..B RAT|Intersec|
|000022d0| 74 73 57 69 74 68 28 5c | 7c 29 0a 77 69 6c 6c 20 |tsWith(\||).will |
|000022e0| 73 65 61 72 63 68 20 66 | 6f 72 20 61 6c 6c 20 72 |search f|or all r|
|000022f0| 65 63 74 61 6e 67 6c 65 | 73 20 77 68 69 63 68 20 |ectangle|s which |
|00002300| 61 72 65 20 63 6f 6e 74 | 61 69 6e 65 64 20 69 6e |are cont|ained in|
|00002310| 20 6f 72 20 69 6e 74 65 | 72 73 65 63 74 20 74 68 | or inte|rsect th|
|00002320| 65 20 72 65 63 74 61 6e | 67 6c 65 20 64 65 66 69 |e rectan|gle defi|
|00002330| 6e 65 64 20 62 79 0a 2e | 42 20 28 78 2c 79 2c 77 |ned by..|B (x,y,w|
|00002340| 2c 68 29 2c 0a 77 68 65 | 72 65 0a 2e 42 20 28 78 |,h),.whe|re..B (x|
|00002350| 2c 79 29 0a 61 72 65 20 | 74 68 65 20 63 65 6e 74 |,y).are |the cent|
|00002360| 65 72 20 6f 66 20 74 68 | 65 20 72 65 63 74 61 6e |er of th|e rectan|
|00002370| 67 6c 65 20 61 6e 64 0a | 2e 42 20 28 77 2c 68 29 |gle and.|.B (w,h)|
|00002380| 0a 61 72 65 20 74 68 65 | 20 64 69 73 74 61 6e 63 |.are the| distanc|
|00002390| 65 73 20 66 72 6f 6d 20 | 74 68 65 20 63 65 6e 74 |es from |the cent|
|000023a0| 65 72 20 74 6f 20 61 6e | 20 65 64 67 65 2e 20 20 |er to an| edge.  |
|000023b0| 28 53 69 6d 69 6c 61 72 | 20 69 6e 20 6e 61 74 75 |(Similar| in natu|
|000023c0| 72 65 20 74 6f 20 74 68 | 65 20 63 65 6e 74 65 72 |re to th|e center|
|000023d0| 20 61 6e 64 20 72 61 64 | 69 69 20 6f 66 20 61 6e | and rad|ii of an|
|000023e0| 20 65 6c 6c 69 70 73 65 | 2c 20 65 78 63 65 70 74 | ellipse|, except|
|000023f0| 20 74 68 61 74 20 69 74 | 20 64 65 66 69 6e 65 73 | that it| defines|
|00002400| 20 61 20 72 65 63 74 61 | 6e 67 6c 65 2e 29 20 20 | a recta|ngle.)  |
|00002410| 41 6c 6c 20 72 65 63 74 | 61 6e 67 6c 65 20 6f 62 |All rect|angle ob|
|00002420| 6a 65 63 74 73 20 73 74 | 6f 72 65 20 69 6e 0a 2e |jects st|ore in..|
|00002430| 42 20 74 72 65 65 0a 61 | 72 65 20 72 65 74 75 72 |B tree.a|re retur|
|00002440| 6e 65 64 20 69 6e 20 61 | 6e 0a 2e 42 20 52 41 54 |ned in a|n..B RAT|
|00002450| 52 65 67 69 6f 6e 4c 69 | 73 74 2e 0a 41 6c 6c 20 |RegionLi|st..All |
|00002460| 75 6e 69 71 75 65 20 72 | 65 63 74 61 6e 67 6c 65 |unique r|ectangle|
|00002470| 73 20 61 72 65 20 72 65 | 70 6f 72 74 65 64 20 6f |s are re|ported o|
|00002480| 6e 63 65 2e 20 20 49 66 | 20 6d 6f 72 65 20 74 68 |nce.  If| more th|
|00002490| 61 6e 20 6f 6e 65 20 6f | 62 6a 65 63 74 20 6f 63 |an one o|bject oc|
|000024a0| 63 75 70 79 20 74 68 65 | 0a 65 78 61 63 74 20 73 |cupy the|.exact s|
|000024b0| 61 6d 65 20 72 65 63 74 | 61 6e 67 6c 65 20 69 6e |ame rect|angle in|
|000024c0| 20 74 68 65 20 67 69 76 | 65 6e 20 52 65 63 74 61 | the giv|en Recta|
|000024d0| 6e 67 6c 65 20 41 63 63 | 65 73 73 20 54 72 65 65 |ngle Acc|ess Tree|
|000024e0| 2c 20 74 68 65 79 20 61 | 72 65 20 72 65 70 6f 72 |, they a|re repor|
|000024f0| 74 65 64 20 69 6e 0a 6c | 69 6e 6b 65 64 20 6c 69 |ted in.l|inked li|
|00002500| 73 74 20 66 6f 72 6d 20 | 61 73 20 64 65 66 69 6e |st form |as defin|
|00002510| 65 64 20 62 79 20 74 68 | 65 0a 2e 42 20 52 41 54 |ed by th|e..B RAT|
|00002520| 4f 62 6a 4c 69 73 74 0a | 74 79 70 65 2e 20 20 28 |ObjList.|type.  (|
|00002530| 53 65 65 0a 2e 42 52 20 | 52 41 54 49 6e 74 72 6f |See..BR |RATIntro|
|00002540| 20 28 33 29 2e 29 0a 54 | 68 65 20 61 63 74 75 61 | (3).).T|he actua|
|00002550| 6c 0a 2e 42 20 52 41 54 | 52 65 67 69 6f 6e 4c 69 |l..B RAT|RegionLi|
|00002560| 73 74 0a 69 73 20 6d 61 | 6c 6c 6f 63 27 64 20 61 |st.is ma|lloc'd a|
|00002570| 6e 64 20 66 6f 72 20 65 | 61 63 68 20 6f 6e 65 20 |nd for e|ach one |
|00002580| 72 65 74 75 72 6e 65 64 | 2c 20 69 74 20 69 73 20 |returned|, it is |
|00002590| 74 68 65 20 63 61 6c 6c | 65 72 27 73 20 72 65 73 |the call|er's res|
|000025a0| 70 6f 6e 73 69 62 69 6c | 69 74 79 20 74 6f 0a 66 |ponsibil|ity to.f|
|000025b0| 72 65 65 20 74 68 65 6d | 2e 20 20 54 68 65 20 63 |ree them|.  The c|
|000025c0| 61 6c 6c 65 72 20 73 68 | 6f 75 6c 64 20 6e 6f 74 |aller sh|ould not|
|000025d0| 20 66 72 65 65 20 74 68 | 65 20 61 63 74 75 61 6c | free th|e actual|
|000025e0| 0a 2e 42 20 52 41 54 52 | 65 67 69 6f 6e 27 73 0a |..B RATR|egion's.|
|000025f0| 63 6f 6e 74 61 69 6e 65 | 64 20 69 6e 20 74 68 65 |containe|d in the|
|00002600| 0a 2e 42 20 52 41 54 52 | 65 67 69 6f 6e 4c 69 73 |..B RATR|egionLis|
|00002610| 74 0a 77 68 69 63 68 20 | 61 72 65 20 72 65 74 75 |t.which |are retu|
|00002620| 72 6e 65 64 2e 20 20 54 | 68 6f 73 65 20 61 72 65 |rned.  T|hose are|
|00002630| 20 6a 75 73 74 20 70 6f | 69 6e 74 65 72 73 20 74 | just po|inters t|
|00002640| 6f 20 61 63 74 75 61 6c | 20 65 6c 65 6d 65 6e 74 |o actual| element|
|00002650| 73 20 6f 66 20 74 68 65 | 20 74 72 65 65 2e 0a 2e |s of the| tree...|
|00002660| 4c 50 0a 2e 53 48 20 53 | 45 45 20 41 4c 53 4f 0a |LP..SH S|EE ALSO.|
|00002670| 2e 42 52 20 52 41 54 43 | 72 65 61 74 65 54 72 65 |.BR RATC|reateTre|
|00002680| 65 20 28 33 29 2c 0a 2e | 42 52 20 52 41 54 44 65 |e (3),..|BR RATDe|
|00002690| 6c 65 74 65 20 28 33 29 | 2c 0a 2e 42 52 20 52 41 |lete (3)|,..BR RA|
|000026a0| 54 49 6e 73 65 72 74 20 | 28 33 29 2c 0a 2e 42 52 |TInsert |(3),..BR|
|000026b0| 20 52 41 54 49 6e 74 72 | 6f 20 28 33 29 2c 0a 2e | RATIntr|o (3),..|
|000026c0| 42 52 20 52 41 54 4e 65 | 61 72 65 73 74 4d 61 74 |BR RATNe|arestMat|
|000026d0| 63 68 20 28 33 29 0a 2e | 66 69 0a 20 20 20 20 20 |ch (3)..|fi.     |
|000026e0| 20 20 20 20 20 20 20 20 | 20 20 20 2a 6f 62 6a 65 |        |   *obje|
|000026f0| 63 74 3b 0a 09 73 74 72 | 75 63 74 20 5f 72 61 74 |ct;..str|uct _rat|
|00002700| 5f 6f 62 6a 5f 6c 69 73 | 74 5f 20 20 20 20 2a 6e |_obj_lis|t_    *n|
|00002710| 65 78 74 3b 0a 7d 20 52 | 41 54 4f 62 6a 4c 69 73 |ext;.} R|ATObjLis|
|00002720| 74 5f 74 2c 20 2a 52 41 | 54 4f 62 6a 4c 69 73 74 |t_t, *RA|TObjList|
|00002730| 3b 0a 0a 74 79 70 65 64 | 65 66 20 73 74 72 75 63 |;..typed|ef struc|
|00002740| 74 20 7b 0a 09 52 41 54 | 56 65 63 74 6f 72 20 20 |t {..RAT|Vector  |
|00002750| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6c |        |       l|
|00002760| 6f 63 61 74 69 6f 6e 3b | 0a 09 52 41 54 4f 62 6a |ocation;|..RATObj|
|00002770| 4c 69 73 74 5f 74 20 20 | 20 20 20 20 20 20 20 20 |List_t  |        |
|00002780| 20 20 20 20 6f 62 6a 5f | 6c 69 73 74 3b 0a 7d 20 |    obj_|list;.} |
|00002790| 2a 52 41 54 52 65 67 69 | 6f 6e 3b 0a 0a 74 79 70 |*RATRegi|on;..typ|
|000027a0| 65 64 65 66 20 73 74 72 | 75 63 74 20 5f 72 61 74 |edef str|uct _rat|
|000027b0| 5f 72 65 67 69 6f 6e 5f | 6c 69 73 74 5f 20 7b 0a |_region_|list_ {.|
|000027c0| 09 52 41 54 52 65 67 69 | 6f 6e 20 20 20 20 20 20 |.RATRegi|on      |
|000027d0| 20 20 20 20 20 20 20 20 | 20 20 20 72 65 67 69 6f |        |   regio|
|000027e0| 6e 3b 0a 09 73 74 72 75 | 63 74 20 5f 72 61 74 5f |n;..stru|ct _rat_|
|000027f0| 72 65 67 69 6f 6e 5f 6c | 69 73 74 5f 20 2a 6e 65 |region_l|ist_ *ne|
|00002800| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00002810| 52 41 54 49 6e 74 65 72 | 73 65 63 74 73 57 69 74 |RATInter|sectsWit|
|00002820| 68 2e 33 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |h.3.....|........|
|00002830| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002840| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002850| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002860| 00 00 00 00 30 30 30 37 | 35 35 20 00 30 30 37 32 |....0007|55 .0072|
|00002870| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00002880| 30 30 30 30 30 30 30 00 | 30 36 33 33 34 33 35 30 |0000000.|06334350|
|00002890| 30 36 36 20 30 32 33 36 | 34 35 00 20 32 52 41 54 |066 0236|45. 2RAT|
|000028a0| 43 6f 6e 74 61 69 6e 65 | 64 57 69 74 68 69 6e 2e |Containe|dWithin.|
|000028b0| 33 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |3.......|........|
|000028c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000028d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000028e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000028f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002900| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00002910| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002920| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00002930| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00002940| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00002950| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00002960| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002970| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002980| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002990| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000029a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000029b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000029c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000029d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000029e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000029f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002a00| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00002a10| 52 41 54 49 6e 73 65 72 | 74 2e 33 00 00 00 00 00 |RATInser|t.3.....|
|00002a20| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002a30| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002a40| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002a50| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002a60| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00002a70| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00002a80| 30 30 30 34 37 34 36 20 | 30 35 37 36 31 33 36 32 |0004746 |05761362|
|00002a90| 31 30 35 20 30 31 36 34 | 37 32 00 20 30 00 00 00 |105 0164|72. 0...|
|00002aa0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002ab0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002ac0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002ad0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002ae0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002af0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002b00| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00002b10| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002b20| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00002b30| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00002b40| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00002b50| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00002b60| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002b70| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002b80| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002b90| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002ba0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002bb0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002bc0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002bd0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002be0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002bf0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00002c00| 2e 54 48 20 52 41 54 49 | 6e 73 65 72 74 20 33 20 |.TH RATI|nsert 3 |
|00002c10| 22 32 35 20 4d 61 79 20 | 31 39 39 35 22 0a 2e 53 |"25 May |1995"..S|
|00002c20| 48 20 4e 41 4d 45 0a 52 | 41 54 49 6e 73 65 72 74 |H NAME.R|ATInsert|
|00002c30| 20 5c 2d 20 47 69 76 65 | 6e 20 61 20 52 65 63 74 | \- Give|n a Rect|
|00002c40| 61 6e 67 6c 65 20 41 63 | 63 65 73 73 20 54 72 65 |angle Ac|cess Tre|
|00002c50| 65 2c 20 69 6e 73 65 72 | 74 20 61 6e 20 61 72 62 |e, inser|t an arb|
|00002c60| 69 74 72 61 72 79 20 6f | 62 6a 65 63 74 20 69 6e |itrary o|bject in|
|00002c70| 74 6f 20 69 74 2e 0a 2e | 4c 50 0a 52 41 54 44 65 |to it...|LP.RATDe|
|00002c80| 6c 65 74 65 20 5c 2d 20 | 47 69 76 65 6e 20 61 20 |lete \- |Given a |
|00002c90| 52 65 63 74 61 6e 67 6c | 65 20 41 63 63 65 73 73 |Rectangl|e Access|
|00002ca0| 20 54 72 65 65 2c 20 64 | 65 6c 65 74 65 20 74 68 | Tree, d|elete th|
|00002cb0| 65 20 6f 62 6a 65 63 74 | 73 20 6f 72 20 61 20 73 |e object|s or a s|
|00002cc0| 75 62 73 65 74 20 6f 66 | 20 74 68 65 20 6f 62 6a |ubset of| the obj|
|00002cd0| 65 63 74 73 20 61 74 20 | 61 20 73 70 65 63 69 66 |ects at |a specif|
|00002ce0| 69 65 64 20 6c 6f 63 61 | 74 69 6f 6e 2e 0a 2e 53 |ied loca|tion...S|
|00002cf0| 48 20 53 59 4e 4f 50 53 | 49 53 0a 2e 4c 50 0a 2e |H SYNOPS|IS..LP..|
|00002d00| 6e 66 0a 2e 66 74 20 42 | 0a 23 69 6e 63 6c 75 64 |nf..ft B|.#includ|
|00002d10| 65 20 22 72 61 74 6c 69 | 62 2e 68 22 0a 2e 66 69 |e "ratli|b.h"..fi|
|00002d20| 0a 2e 4c 50 0a 2e 6e 66 | 0a 2e 66 74 20 42 0a 76 |..LP..nf|..ft B.v|
|00002d30| 6f 69 64 20 52 41 54 49 | 6e 73 65 72 74 28 74 72 |oid RATI|nsert(tr|
|00002d40| 65 65 2c 20 78 2c 20 79 | 2c 20 77 2c 20 68 2c 20 |ee, x, y|, w, h, |
|00002d50| 6f 62 6a 65 63 74 29 0a | 09 52 41 54 54 72 65 65 |object).|.RATTree|
|00002d60| 20 74 72 65 65 3b 0a 09 | 69 6e 74 33 32 20 78 2c | tree;..|int32 x,|
|00002d70| 20 79 2c 20 77 2c 20 68 | 3b 0a 09 76 6f 69 64 20 | y, w, h|;..void |
|00002d80| 2a 6f 62 6a 65 63 74 3b | 0a 0a 69 6e 74 20 52 41 |*object;|..int RA|
|00002d90| 54 44 65 6c 65 74 65 28 | 74 72 65 65 2c 20 78 2c |TDelete(|tree, x,|
|00002da0| 20 79 2c 20 77 2c 20 68 | 2c 20 6f 62 6a 5f 6c 69 | y, w, h|, obj_li|
|00002db0| 73 74 29 0a 09 52 41 54 | 54 72 65 65 20 74 72 65 |st)..RAT|Tree tre|
|00002dc0| 65 3b 0a 09 69 6e 74 33 | 32 20 78 2c 20 79 2c 20 |e;..int3|2 x, y, |
|00002dd0| 77 2c 20 68 3b 0a 09 52 | 41 54 4f 62 6a 4c 69 73 |w, h;..R|ATObjLis|
|00002de0| 74 20 6f 62 6a 5f 6c 69 | 73 74 3b 0a 2e 66 74 0a |t obj_li|st;..ft.|
|00002df0| 2e 66 69 0a 2e 49 58 20 | 22 52 41 54 49 6e 73 65 |.fi..IX |"RATInse|
|00002e00| 72 74 28 29 22 20 22 69 | 6e 73 65 72 74 20 6f 62 |rt()" "i|nsert ob|
|00002e10| 6a 65 63 74 20 69 6e 74 | 6f 20 52 41 54 22 0a 2e |ject int|o RAT"..|
|00002e20| 49 58 20 22 52 41 54 44 | 65 6c 65 74 65 28 29 22 |IX "RATD|elete()"|
|00002e30| 20 22 64 65 6c 65 74 65 | 20 6f 62 6a 65 63 74 73 | "delete| objects|
|00002e40| 20 66 72 6f 6d 20 52 41 | 54 22 0a 2e 53 48 20 44 | from RA|T"..SH D|
|00002e50| 45 53 43 52 49 50 54 49 | 4f 4e 0a 2e 4c 50 0a 2e |ESCRIPTI|ON..LP..|
|00002e60| 42 20 52 41 54 49 6e 73 | 65 72 74 28 5c 29 0a 77 |B RATIns|ert(\).w|
|00002e70| 69 6c 6c 20 69 6e 73 65 | 72 74 20 61 20 6e 65 77 |ill inse|rt a new|
|00002e80| 20 6f 62 6a 65 63 74 20 | 69 6e 74 6f 20 74 68 65 | object |into the|
|00002e90| 20 52 65 63 74 61 6e 67 | 6c 65 20 41 63 63 65 73 | Rectang|le Acces|
|00002ea0| 73 20 54 72 65 65 2e 20 | 20 54 68 65 20 6f 62 6a |s Tree. | The obj|
|00002eb0| 65 63 74 20 69 73 0a 64 | 65 73 63 72 69 62 65 64 |ect is.d|escribed|
|00002ec0| 20 61 6e 64 20 72 65 66 | 65 72 65 6e 63 65 64 20 | and ref|erenced |
|00002ed0| 62 79 20 74 68 65 20 72 | 65 63 74 61 6e 67 6c 65 |by the r|ectangle|
|00002ee0| 20 69 74 20 6f 63 63 75 | 70 69 65 73 20 69 6e 20 | it occu|pies in |
|00002ef0| 32 2d 44 20 73 70 61 63 | 65 2e 0a 41 73 20 64 65 |2-D spac|e..As de|
|00002f00| 73 63 72 69 62 65 64 20 | 69 6e 0a 2e 42 52 20 52 |scribed |in..BR R|
|00002f10| 41 54 69 6e 74 72 6f 20 | 28 33 29 2c 0a 72 65 63 |ATintro |(3),.rec|
|00002f20| 74 61 6e 67 6c 65 73 20 | 61 72 65 20 64 65 66 69 |tangles |are defi|
|00002f30| 6e 65 64 20 62 79 0a 2e | 42 20 28 78 2c 79 2c 77 |ned by..|B (x,y,w|
|00002f40| 2c 68 29 2c 0a 77 68 65 | 72 65 0a 2e 42 20 28 78 |,h),.whe|re..B (x|
|00002f50| 2c 79 29 0a 61 72 65 20 | 74 68 65 20 63 65 6e 74 |,y).are |the cent|
|00002f60| 65 72 20 6f 66 20 74 68 | 65 20 72 65 63 74 61 6e |er of th|e rectan|
|00002f70| 67 6c 65 20 61 6e 64 0a | 2e 42 20 28 77 2c 68 29 |gle and.|.B (w,h)|
|00002f80| 0a 61 72 65 20 74 68 65 | 20 64 69 73 74 61 6e 63 |.are the| distanc|
|00002f90| 65 73 20 66 72 6f 6d 20 | 74 68 65 20 63 65 6e 74 |es from |the cent|
|00002fa0| 65 72 20 74 6f 20 61 6e | 20 65 64 67 65 2e 20 20 |er to an| edge.  |
|00002fb0| 28 53 69 6d 69 6c 61 72 | 20 69 6e 20 6e 61 74 75 |(Similar| in natu|
|00002fc0| 72 65 20 74 6f 20 74 68 | 65 20 63 65 6e 74 65 72 |re to th|e center|
|00002fd0| 0a 61 6e 64 20 72 61 64 | 69 69 20 6f 66 20 61 6e |.and rad|ii of an|
|00002fe0| 20 65 6c 6c 69 70 73 65 | 2c 20 65 78 63 65 70 74 | ellipse|, except|
|00002ff0| 20 74 68 61 74 20 69 74 | 20 64 65 66 69 6e 65 73 | that it| defines|
|00003000| 20 61 20 72 65 63 74 61 | 6e 67 6c 65 2e 29 0a 54 | a recta|ngle.).T|
|00003010| 68 65 20 61 63 74 75 61 | 6c 20 6f 62 6a 65 63 74 |he actua|l object|
|00003020| 2c 20 61 0a 2e 42 20 28 | 76 6f 69 64 20 2a 29 2c |, a..B (|void *),|
|00003030| 0a 63 61 6e 20 62 65 20 | 61 6e 79 74 68 69 6e 67 |.can be |anything|
|00003040| 20 79 6f 75 20 77 69 73 | 68 2c 20 69 6e 63 6c 75 | you wis|h, inclu|
|00003050| 64 69 6e 67 20 61 20 6e | 6f 6e 2d 70 6f 69 6e 74 |ding a n|on-point|
|00003060| 65 72 2c 20 61 73 20 6c | 6f 6e 67 20 61 73 20 69 |er, as l|ong as i|
|00003070| 74 20 6f 63 63 75 70 69 | 65 73 0a 74 68 65 20 73 |t occupi|es.the s|
|00003080| 61 6d 65 20 61 6d 6f 75 | 6e 74 20 6f 66 20 73 70 |ame amou|nt of sp|
|00003090| 61 63 65 20 61 73 20 61 | 20 70 6f 69 6e 74 65 72 |ace as a| pointer|
|000030a0| 20 6f 6e 20 79 6f 75 72 | 20 6d 61 63 68 69 6e 65 | on your| machine|
|000030b0| 2e 20 20 54 68 69 73 20 | 66 75 6e 63 74 69 6f 6e |.  This |function|
|000030c0| 20 68 61 73 20 6e 6f 0a | 72 65 74 75 72 6e 20 76 | has no.|return v|
|000030d0| 61 6c 75 65 2e 0a 2e 4c | 50 0a 2e 42 20 52 41 54 |alue...L|P..B RAT|
|000030e0| 44 65 6c 65 74 65 28 5c | 29 0a 77 69 6c 6c 20 64 |Delete(\|).will d|
|000030f0| 65 6c 65 74 65 20 61 6c | 6c 20 6f 62 6a 65 63 74 |elete al|l object|
|00003100| 73 20 6f 72 20 61 20 73 | 75 62 73 65 74 20 6f 66 |s or a s|ubset of|
|00003110| 20 6f 62 6a 65 63 74 73 | 20 77 68 69 63 68 20 6f | objects| which o|
|00003120| 63 63 75 70 79 20 61 20 | 67 69 76 65 6e 20 72 65 |ccupy a |given re|
|00003130| 63 74 61 6e 67 6c 65 2e | 0a 49 66 20 79 6f 75 20 |ctangle.|.If you |
|00003140| 77 69 73 68 20 74 6f 20 | 64 65 6c 65 74 65 20 61 |wish to |delete a|
|00003150| 6c 6c 20 6f 62 6a 65 63 | 74 73 20 77 68 69 63 68 |ll objec|ts which|
|00003160| 20 6f 63 63 75 70 79 20 | 61 20 73 69 6e 67 6c 65 | occupy |a single|
|00003170| 20 72 65 63 74 61 6e 67 | 6c 65 2c 20 79 6f 75 20 | rectang|le, you |
|00003180| 63 61 6e 0a 73 69 6d 70 | 6c 79 20 70 61 73 73 0a |can.simp|ly pass.|
|00003190| 2e 42 20 4e 55 4c 4c 0a | 61 73 20 79 6f 75 72 0a |.B NULL.|as your.|
|000031a0| 2e 42 20 6f 62 6a 5f 6c | 69 73 74 2e 0a 49 66 20 |.B obj_l|ist..If |
|000031b0| 6d 6f 72 65 20 74 68 61 | 6e 20 6f 6e 65 20 6f 62 |more tha|n one ob|
|000031c0| 6a 65 63 74 20 6f 63 63 | 75 70 69 65 73 20 61 20 |ject occ|upies a |
|000031d0| 73 69 6e 67 6c 65 20 72 | 65 63 74 61 6e 67 6c 65 |single r|ectangle|
|000031e0| 20 61 6e 64 20 79 6f 75 | 20 77 69 73 68 20 74 6f | and you| wish to|
|000031f0| 20 6f 6e 6c 79 20 64 65 | 6c 65 74 65 0a 61 20 73 | only de|lete.a s|
|00003200| 75 62 73 65 74 20 6f 66 | 20 74 68 65 6d 2c 20 79 |ubset of| them, y|
|00003210| 6f 75 20 63 61 6e 20 70 | 61 73 73 20 74 68 65 20 |ou can p|ass the |
|00003220| 73 75 62 73 65 74 20 69 | 6e 20 61 6e 20 52 41 54 |subset i|n an RAT|
|00003230| 4f 62 6a 4c 69 73 74 2c | 20 61 20 6c 69 6e 6b 65 |ObjList,| a linke|
|00003240| 64 20 6c 69 73 74 20 6f | 66 0a 74 79 70 65 0a 2e |d list o|f.type..|
|00003250| 42 20 28 76 6f 69 64 20 | 2a 29 2e 0a 41 6e 20 65 |B (void |*)..An e|
|00003260| 71 75 61 6c 69 74 79 20 | 63 68 65 63 6b 20 69 73 |quality |check is|
|00003270| 20 70 65 72 66 6f 72 6d | 65 64 20 6f 6e 20 74 68 | perform|ed on th|
|00003280| 65 20 6f 62 6a 65 63 74 | 73 20 74 6f 20 73 65 65 |e object|s to see|
|00003290| 20 69 66 20 61 20 70 61 | 72 74 69 63 75 6c 61 72 | if a pa|rticular|
|000032a0| 20 69 74 65 6d 0a 66 6f | 75 6e 64 20 61 74 20 74 | item.fo|und at t|
|000032b0| 68 65 20 67 69 76 65 6e | 20 6c 6f 63 61 74 69 6f |he given| locatio|
|000032c0| 6e 20 6d 61 74 63 68 65 | 73 20 6f 6e 65 20 6f 66 |n matche|s one of|
|000032d0| 20 74 68 65 20 6f 62 6a | 65 63 74 73 20 69 6e 20 | the obj|ects in |
|000032e0| 74 68 65 20 6c 69 73 74 | 2e 20 20 54 68 69 73 20 |the list|.  This |
|000032f0| 6d 65 61 6e 73 0a 74 68 | 61 74 20 69 66 20 79 6f |means.th|at if yo|
|00003300| 75 20 61 72 65 20 75 73 | 69 6e 67 20 74 68 65 0a |u are us|ing the.|
|00003310| 2e 42 20 6f 62 6a 65 63 | 74 0a 66 69 65 6c 64 20 |.B objec|t.field |
|00003320| 74 6f 20 70 6f 69 6e 74 | 20 74 6f 20 61 20 73 74 |to point| to a st|
|00003330| 72 75 63 74 75 72 65 2c | 20 74 68 65 20 74 65 73 |ructure,| the tes|
|00003340| 74 20 70 65 72 66 6f 72 | 6d 65 64 20 69 73 20 70 |t perfor|med is p|
|00003350| 6f 69 6e 74 65 72 20 65 | 71 75 61 6c 69 74 79 2c |ointer e|quality,|
|00003360| 20 73 6f 0a 61 20 70 6f | 69 6e 74 65 72 20 74 6f | so.a po|inter to|
|00003370| 20 61 20 73 65 70 61 72 | 61 74 65 20 63 6f 70 79 | a separ|ate copy|
|00003380| 20 6f 66 20 74 68 65 20 | 73 61 6d 65 20 73 74 72 | of the |same str|
|00003390| 75 63 74 75 72 65 20 77 | 69 6c 6c 20 6e 6f 74 20 |ucture w|ill not |
|000033a0| 6d 61 74 63 68 2e 0a 28 | 49 66 20 79 6f 75 20 66 |match..(|If you f|
|000033b0| 69 6e 64 20 74 68 61 74 | 20 79 6f 75 20 6e 65 65 |ind that| you nee|
|000033c0| 64 20 61 6e 20 65 71 75 | 61 6c 69 74 79 20 63 68 |d an equ|ality ch|
|000033d0| 65 63 6b 65 72 2c 20 49 | 27 6d 20 73 75 72 65 20 |ecker, I|'m sure |
|000033e0| 69 74 20 77 6f 75 6c 64 | 6e 27 74 20 62 65 20 68 |it would|n't be h|
|000033f0| 61 72 64 0a 74 6f 20 6d | 6f 64 69 66 79 20 74 68 |ard.to m|odify th|
|00003400| 65 20 63 6f 64 65 20 74 | 6f 20 64 6f 20 74 68 69 |e code t|o do thi|
|00003410| 73 2e 29 20 20 54 68 69 | 73 20 66 75 6e 63 74 69 |s.)  Thi|s functi|
|00003420| 6f 6e 20 72 65 74 75 72 | 6e 73 20 6e 6f 6e 2d 7a |on retur|ns non-z|
|00003430| 65 72 6f 20 69 66 20 6e | 6f 74 68 69 6e 67 20 77 |ero if n|othing w|
|00003440| 61 73 0a 64 65 6c 65 74 | 65 64 20 61 6e 64 20 7a |as.delet|ed and z|
|00003450| 65 72 6f 20 69 66 20 73 | 6f 6d 65 74 68 69 6e 67 |ero if s|omething|
|00003460| 20 77 61 73 20 64 65 6c | 65 74 65 64 2e 0a 2e 4c | was del|eted...L|
|00003470| 50 0a 42 6f 74 68 20 6f | 70 65 72 61 74 69 6f 6e |P.Both o|peration|
|00003480| 73 20 72 75 6e 20 69 6e | 20 61 6d 6f 72 74 69 7a |s run in| amortiz|
|00003490| 65 64 0a 2e 42 20 4f 28 | 6c 6f 67 28 6e 29 29 0a |ed..B O(|log(n)).|
|000034a0| 74 69 6d 65 2e 20 20 41 | 6e 79 20 70 61 72 74 69 |time.  A|ny parti|
|000034b0| 63 75 6c 61 72 20 69 6e | 73 65 72 74 20 6f 72 20 |cular in|sert or |
|000034c0| 64 65 6c 65 74 65 20 63 | 61 6e 20 74 61 6b 65 20 |delete c|an take |
|000034d0| 75 70 20 74 6f 0a 2e 42 | 20 4f 28 6e 2a 6c 6f 67 |up to..B| O(n*log|
|000034e0| 28 6e 29 29 0a 74 69 6d | 65 2c 20 62 75 74 20 74 |(n)).tim|e, but t|
|000034f0| 68 69 73 20 6f 6e 6c 79 | 20 68 61 70 70 65 6e 73 |his only| happens|
|00003500| 20 61 66 74 65 72 20 72 | 6f 75 67 68 6c 79 20 68 | after r|oughly h|
|00003510| 61 6c 66 20 74 68 65 20 | 72 65 63 74 61 6e 67 6c |alf the |rectangl|
|00003520| 65 73 20 68 61 76 65 20 | 62 65 65 6e 20 64 65 6c |es have |been del|
|00003530| 65 74 65 64 2c 0a 6f 72 | 20 74 68 65 20 6e 75 6d |eted,.or| the num|
|00003540| 62 65 72 20 6f 66 20 72 | 65 63 74 61 6e 67 6c 65 |ber of r|ectangle|
|00003550| 73 20 68 61 73 20 64 6f | 75 62 6c 65 64 2e 0a 2e |s has do|ubled...|
|00003560| 53 48 20 53 45 45 20 41 | 4c 53 4f 0a 2e 42 52 20 |SH SEE A|LSO..BR |
|00003570| 52 41 54 43 6f 6e 74 61 | 69 6e 65 64 57 69 74 68 |RATConta|inedWith|
|00003580| 69 6e 20 28 33 29 2c 0a | 2e 42 52 20 52 41 54 43 |in (3),.|.BR RATC|
|00003590| 72 65 61 74 65 54 72 65 | 65 20 28 33 29 2c 0a 2e |reateTre|e (3),..|
|000035a0| 42 52 20 52 41 54 49 6e | 74 65 72 73 65 63 74 73 |BR RATIn|tersects|
|000035b0| 57 69 74 68 20 28 33 29 | 2c 0a 2e 42 52 20 52 41 |With (3)|,..BR RA|
|000035c0| 54 49 6e 74 72 6f 20 28 | 33 29 2c 0a 2e 42 52 20 |TIntro (|3),..BR |
|000035d0| 52 41 54 4e 65 61 72 65 | 73 74 4d 61 74 63 68 20 |RATNeare|stMatch |
|000035e0| 28 33 29 0a 0a 0a 2c 20 | 52 41 54 49 6e 73 65 72 |(3)..., |RATInser|
|000035f0| 74 2c 0a 61 6e 64 20 0a | 2e 42 20 52 41 54 44 65 |t,.and .|.B RATDe|
|00003600| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00003610| 52 41 54 44 65 6c 65 74 | 65 2e 33 00 00 00 00 00 |RATDelet|e.3.....|
|00003620| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003630| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003640| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003650| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003660| 00 00 00 00 30 30 30 37 | 35 35 20 00 30 30 37 32 |....0007|55 .0072|
|00003670| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00003680| 30 30 30 30 30 30 30 00 | 30 36 33 33 34 33 35 30 |0000000.|06334350|
|00003690| 30 36 36 20 30 32 30 32 | 34 35 00 20 32 52 41 54 |066 0202|45. 2RAT|
|000036a0| 49 6e 73 65 72 74 2e 33 | 00 00 00 00 00 00 00 00 |Insert.3|........|
|000036b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003700| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00003710| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003720| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00003730| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00003740| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00003750| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00003760| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003770| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003780| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003790| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003800| 72 61 74 6c 69 62 2f 6d | 61 6e 2f 6d 61 6e 33 2f |ratlib/m|an/man3/|
|00003810| 52 41 54 4e 65 61 72 65 | 73 74 4d 61 74 63 68 2e |RATNeare|stMatch.|
|00003820| 33 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |3.......|........|
|00003830| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003840| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003850| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003860| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00003870| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00003880| 30 30 30 32 35 32 35 20 | 30 35 37 36 31 33 36 32 |0002525 |05761362|
|00003890| 31 30 36 20 30 31 37 35 | 37 36 00 20 30 00 00 00 |106 0175|76. 0...|
|000038a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003900| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00003910| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003920| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00003930| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00003940| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00003950| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00003960| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003970| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003980| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003990| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000039a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000039b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000039c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000039d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000039e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000039f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003a00| 2e 54 48 20 52 41 54 4e | 65 61 72 65 73 74 4d 61 |.TH RATN|earestMa|
|00003a10| 74 63 68 20 33 20 22 32 | 35 20 4d 61 79 20 31 39 |tch 3 "2|5 May 19|
|00003a20| 39 35 22 0a 2e 53 48 20 | 4e 41 4d 45 0a 52 41 54 |95"..SH |NAME.RAT|
|00003a30| 4e 65 61 72 65 73 74 4d | 61 74 63 68 20 5c 2d 20 |NearestM|atch \- |
|00003a40| 47 69 76 65 6e 20 61 20 | 52 65 63 74 61 6e 67 6c |Given a |Rectangl|
|00003a50| 65 20 41 63 63 65 73 73 | 20 54 72 65 65 20 61 6e |e Access| Tree an|
|00003a60| 64 20 61 20 71 75 65 72 | 79 20 72 65 63 74 61 6e |d a quer|y rectan|
|00003a70| 67 6c 65 2c 20 72 65 74 | 75 72 6e 20 65 69 74 68 |gle, ret|urn eith|
|00003a80| 65 72 20 61 6e 20 65 78 | 61 63 74 20 6d 61 74 63 |er an ex|act matc|
|00003a90| 68 2c 20 6f 72 20 61 20 | 22 63 6c 6f 73 65 22 20 |h, or a |"close" |
|00003aa0| 6d 61 74 63 68 0a 2e 4c | 50 0a 2e 53 48 20 53 59 |match..L|P..SH SY|
|00003ab0| 4e 4f 50 53 49 53 0a 2e | 4c 50 0a 2e 6e 66 0a 2e |NOPSIS..|LP..nf..|
|00003ac0| 66 74 20 42 0a 23 69 6e | 63 6c 75 64 65 20 22 72 |ft B.#in|clude "r|
|00003ad0| 61 74 6c 69 62 2e 68 22 | 0a 2e 66 69 0a 2e 4c 50 |atlib.h"|..fi..LP|
|00003ae0| 0a 2e 6e 66 0a 2e 66 74 | 20 42 0a 52 41 54 52 65 |..nf..ft| B.RATRe|
|00003af0| 67 69 6f 6e 20 52 41 54 | 4e 65 61 72 65 73 74 4d |gion RAT|NearestM|
|00003b00| 61 74 63 68 28 74 72 65 | 65 2c 20 78 2c 20 79 2c |atch(tre|e, x, y,|
|00003b10| 20 77 2c 20 68 29 0a 09 | 52 41 54 54 72 65 65 20 | w, h)..|RATTree |
|00003b20| 74 72 65 65 3b 0a 09 69 | 6e 74 33 32 20 78 2c 20 |tree;..i|nt32 x, |
|00003b30| 79 2c 20 77 2c 20 68 3b | 0a 2e 66 74 0a 2e 66 69 |y, w, h;|..ft..fi|
|00003b40| 0a 2e 49 58 20 22 52 41 | 54 4e 65 61 72 65 73 74 |..IX "RA|TNearest|
|00003b50| 4d 61 74 63 68 28 29 22 | 20 22 67 65 74 20 6f 62 |Match()"| "get ob|
|00003b60| 6a 65 63 74 20 66 72 6f | 6d 20 52 41 54 22 0a 2e |ject fro|m RAT"..|
|00003b70| 53 48 20 44 45 53 43 52 | 49 50 54 49 4f 4e 0a 2e |SH DESCR|IPTION..|
|00003b80| 4c 50 0a 2e 42 20 52 41 | 54 4e 65 61 72 65 73 74 |LP..B RA|TNearest|
|00003b90| 4d 61 74 63 68 28 5c 29 | 0a 69 73 20 75 73 65 64 |Match(\)|.is used|
|00003ba0| 20 74 6f 20 71 75 65 72 | 79 20 66 6f 72 20 70 61 | to quer|y for pa|
|00003bb0| 72 74 69 63 75 6c 61 72 | 20 72 65 63 74 61 6e 67 |rticular| rectang|
|00003bc0| 6c 65 73 20 69 6e 20 74 | 68 65 20 52 65 63 74 61 |les in t|he Recta|
|00003bd0| 6e 67 6c 65 20 41 63 63 | 65 73 73 20 54 72 65 65 |ngle Acc|ess Tree|
|00003be0| 2e 20 20 49 66 20 61 6e | 0a 65 78 61 63 74 20 6d |.  If an|.exact m|
|00003bf0| 61 74 63 68 20 65 78 69 | 73 74 73 2c 20 69 74 20 |atch exi|sts, it |
|00003c00| 69 73 20 67 75 61 72 61 | 6e 74 65 65 64 20 74 6f |is guara|nteed to|
|00003c10| 20 62 65 20 72 65 74 75 | 72 6e 65 64 20 69 6e 20 | be retu|rned in |
|00003c20| 61 0a 2e 42 20 52 41 54 | 52 65 67 69 6f 6e 0a 73 |a..B RAT|Region.s|
|00003c30| 74 72 75 63 74 75 72 65 | 2e 20 20 54 68 69 73 20 |tructure|.  This |
|00003c40| 73 74 72 75 63 74 75 72 | 65 20 63 6f 6e 74 61 69 |structur|e contai|
|00003c50| 6e 73 20 61 6c 6c 20 74 | 68 65 20 6f 62 6a 65 63 |ns all t|he objec|
|00003c60| 74 73 20 61 74 20 74 68 | 65 20 70 61 72 74 69 63 |ts at th|e partic|
|00003c70| 75 6c 61 72 20 6c 6f 63 | 61 74 69 6f 6e 2e 0a 49 |ular loc|ation..I|
|00003c80| 66 20 74 68 65 72 65 20 | 69 73 20 6e 6f 20 65 78 |f there |is no ex|
|00003c90| 61 63 74 20 6d 61 74 63 | 68 2c 20 68 6f 77 65 76 |act matc|h, howev|
|00003ca0| 65 72 2c 20 61 20 22 63 | 6c 6f 73 65 22 20 72 65 |er, a "c|lose" re|
|00003cb0| 67 69 6f 6e 20 69 73 20 | 72 65 74 75 72 6e 65 64 |gion is |returned|
|00003cc0| 2e 20 20 49 6e 20 74 68 | 69 73 0a 73 65 6e 73 65 |.  In th|is.sense|
|00003cd0| 2c 20 63 6c 6f 73 65 20 | 69 73 20 6d 65 61 73 75 |, close |is measu|
|00003ce0| 72 65 64 20 62 6f 74 68 | 20 69 6e 20 63 65 6e 74 |red both| in cent|
|00003cf0| 65 72 20 70 6f 69 6e 74 | 20 6c 6f 63 61 74 69 6f |er point| locatio|
|00003d00| 6e 20 61 6e 64 20 69 6e | 20 72 65 63 74 61 6e 67 |n and in| rectang|
|00003d10| 6c 65 0a 77 69 64 74 68 | 20 61 6e 64 20 68 65 69 |le.width| and hei|
|00003d20| 67 68 74 2e 0a 41 73 20 | 64 65 73 63 72 69 62 65 |ght..As |describe|
|00003d30| 64 20 69 6e 0a 2e 42 52 | 20 52 41 54 69 6e 74 72 |d in..BR| RATintr|
|00003d40| 6f 20 28 33 29 2c 0a 72 | 65 63 74 61 6e 67 6c 65 |o (3),.r|ectangle|
|00003d50| 73 20 61 72 65 20 64 65 | 66 69 6e 65 64 20 62 79 |s are de|fined by|
|00003d60| 0a 2e 42 20 28 78 2c 79 | 2c 77 2c 68 29 2c 0a 77 |..B (x,y|,w,h),.w|
|00003d70| 68 65 72 65 0a 2e 42 20 | 28 78 2c 79 29 0a 61 72 |here..B |(x,y).ar|
|00003d80| 65 20 74 68 65 20 63 65 | 6e 74 65 72 20 6f 66 20 |e the ce|nter of |
|00003d90| 74 68 65 20 72 65 63 74 | 61 6e 67 6c 65 20 61 6e |the rect|angle an|
|00003da0| 64 0a 2e 42 20 28 77 2c | 68 29 0a 61 72 65 20 74 |d..B (w,|h).are t|
|00003db0| 68 65 20 64 69 73 74 61 | 6e 63 65 73 20 66 72 6f |he dista|nces fro|
|00003dc0| 6d 20 74 68 65 20 63 65 | 6e 74 65 72 20 74 6f 20 |m the ce|nter to |
|00003dd0| 61 6e 20 65 64 67 65 2e | 20 20 28 53 69 6d 69 6c |an edge.|  (Simil|
|00003de0| 61 72 20 69 6e 20 6e 61 | 74 75 72 65 20 74 6f 20 |ar in na|ture to |
|00003df0| 74 68 65 20 63 65 6e 74 | 65 72 0a 61 6e 64 20 72 |the cent|er.and r|
|00003e00| 61 64 69 69 20 6f 66 20 | 61 6e 20 65 6c 6c 69 70 |adii of |an ellip|
|00003e10| 73 65 2c 20 65 78 63 65 | 70 74 20 74 68 61 74 20 |se, exce|pt that |
|00003e20| 69 74 20 64 65 66 69 6e | 65 73 20 61 20 72 65 63 |it defin|es a rec|
|00003e30| 74 61 6e 67 6c 65 2e 29 | 0a 54 68 65 0a 2e 42 20 |tangle.)|.The..B |
|00003e40| 52 41 54 52 65 67 69 6f | 6e 0a 77 68 69 63 68 20 |RATRegio|n.which |
|00003e50| 69 73 20 72 65 74 75 72 | 6e 65 64 20 69 73 0a 2e |is retur|ned is..|
|00003e60| 42 20 6e 6f 74 0a 67 75 | 61 72 61 6e 74 65 65 64 |B not.gu|aranteed|
|00003e70| 20 74 6f 20 62 65 20 74 | 68 65 20 63 6c 6f 73 65 | to be t|he close|
|00003e80| 73 74 20 6d 61 74 63 68 | 2e 20 20 54 68 69 73 20 |st match|.  This |
|00003e90| 6f 70 65 72 61 74 69 6f | 6e 20 72 75 6e 73 20 69 |operatio|n runs i|
|00003ea0| 6e 20 61 6d 6f 72 74 69 | 7a 65 64 0a 2e 42 20 4f |n amorti|zed..B O|
|00003eb0| 28 6c 6f 67 28 6e 29 29 | 0a 74 69 6d 65 2e 0a 2e |(log(n))|.time...|
|00003ec0| 4c 50 0a 2e 53 48 20 53 | 45 45 20 41 4c 53 4f 0a |LP..SH S|EE ALSO.|
|00003ed0| 2e 42 52 20 52 41 54 43 | 6f 6e 74 61 69 6e 65 64 |.BR RATC|ontained|
|00003ee0| 57 69 74 68 69 6e 20 28 | 33 29 2c 0a 2e 42 52 20 |Within (|3),..BR |
|00003ef0| 52 41 54 43 72 65 61 74 | 65 54 72 65 65 20 28 33 |RATCreat|eTree (3|
|00003f00| 29 2c 0a 2e 42 52 20 52 | 41 54 44 65 6c 65 74 65 |),..BR R|ATDelete|
|00003f10| 20 28 33 29 2c 0a 2e 42 | 52 20 52 41 54 49 6e 73 | (3),..B|R RATIns|
|00003f20| 65 72 74 20 28 33 29 2c | 0a 2e 42 52 20 52 41 54 |ert (3),|..BR RAT|
|00003f30| 49 6e 74 65 72 73 65 63 | 74 73 57 69 74 68 20 28 |Intersec|tsWith (|
|00003f40| 33 29 2c 0a 2e 42 52 20 | 52 41 54 49 6e 74 72 6f |3),..BR |RATIntro|
|00003f50| 20 28 33 29 0a 6a 65 63 | 74 73 20 77 68 69 63 68 | (3).jec|ts which|
|00003f60| 20 6f 63 63 75 70 79 20 | 61 20 73 69 6e 67 6c 65 | occupy |a single|
|00003f70| 20 72 65 63 74 61 6e 67 | 6c 65 2c 20 79 6f 75 20 | rectang|le, you |
|00003f80| 63 61 6e 0a 73 69 6d 70 | 6c 79 20 70 61 73 73 0a |can.simp|ly pass.|
|00003f90| 2e 42 20 4e 55 4c 4c 0a | 61 73 20 79 6f 75 72 0a |.B NULL.|as your.|
|00003fa0| 2e 42 20 6f 62 6a 5f 6c | 69 73 74 2e 0a 49 66 20 |.B obj_l|ist..If |
|00003fb0| 6d 6f 72 65 20 74 68 61 | 6e 20 6f 6e 65 20 6f 62 |more tha|n one ob|
|00003fc0| 6a 65 63 74 20 6f 63 63 | 75 70 69 65 73 20 61 20 |ject occ|upies a |
|00003fd0| 73 69 6e 67 6c 65 20 72 | 65 63 74 61 6e 67 6c 65 |single r|ectangle|
|00003fe0| 20 61 6e 64 20 79 6f 75 | 20 77 69 73 68 20 74 6f | and you| wish to|
|00003ff0| 20 6f 6e 6c 79 20 64 65 | 6c 65 74 65 0a 61 20 73 | only de|lete.a s|
|00004000| 72 61 74 6c 69 62 2f 73 | 72 63 2f 00 00 00 00 00 |ratlib/s|rc/.....|
|00004010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004040| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004050| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004060| 00 00 00 00 30 30 30 37 | 37 35 20 00 30 30 37 32 |....0007|75 .0072|
|00004070| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00004080| 30 30 30 30 30 30 30 20 | 30 36 31 37 30 33 31 31 |0000000 |06170311|
|00004090| 37 34 32 20 30 31 33 37 | 33 34 00 20 35 00 00 00 |742 0137|34. 5...|
|000040a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000040b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000040c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000040d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000040e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000040f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004100| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00004110| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004120| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00004130| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00004140| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00004150| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00004160| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004170| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004180| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004190| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000041a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000041b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000041c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000041d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000041e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000041f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004200| 72 61 74 6c 69 62 2f 73 | 72 63 2f 4d 61 6b 65 66 |ratlib/s|rc/Makef|
|00004210| 69 6c 65 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |ile.....|........|
|00004220| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004230| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004240| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004250| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004260| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00004270| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00004280| 30 30 30 31 31 35 36 20 | 30 36 31 37 30 33 31 30 |0001156 |06170310|
|00004290| 32 34 35 20 30 31 35 33 | 37 32 00 20 30 00 00 00 |245 0153|72. 0...|
|000042a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000042b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000042c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000042d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000042e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000042f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004300| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00004310| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004320| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00004330| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00004340| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00004350| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00004360| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004370| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004380| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004390| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000043a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000043b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000043c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000043d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000043e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000043f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004400| 69 6e 63 6c 75 64 65 20 | 2e 2f 6d 61 6b 65 2e 63 |include |./make.c|
|00004410| 6f 6e 66 0a 43 49 4e 43 | 4c 55 44 45 53 3d 2d 49 |onf.CINC|LUDES=-I|
|00004420| 2e 20 2d 49 2e 2e 2f 69 | 6e 63 6c 75 64 65 20 0a |. -I../i|nclude .|
|00004430| 4f 42 4a 53 3d 64 6b 64 | 74 72 65 65 2e 6f 20 73 |OBJS=dkd|tree.o s|
|00004440| 70 6c 61 79 6d 69 6e 2e | 6f 20 72 61 74 6c 69 62 |playmin.|o ratlib|
|00004450| 2e 6f 0a 53 52 43 53 3d | 64 6b 64 74 72 65 65 2e |.o.SRCS=|dkdtree.|
|00004460| 63 20 73 70 6c 61 79 6d | 69 6e 2e 63 20 72 61 74 |c splaym|in.c rat|
|00004470| 6c 69 62 2e 63 0a 43 46 | 4c 41 47 53 3d 24 28 43 |lib.c.CF|LAGS=$(C|
|00004480| 4f 50 54 53 29 20 24 28 | 43 49 4e 43 4c 55 44 45 |OPTS) $(|CINCLUDE|
|00004490| 53 29 0a 41 4c 4c 3d 24 | 28 4f 42 4a 53 29 0a 4c |S).ALL=$|(OBJS).L|
|000044a0| 49 42 53 3d 2d 6c 6d 0a | 0a 61 6c 6c 3a 20 24 28 |IBS=-lm.|.all: $(|
|000044b0| 41 4c 4c 29 0a 0a 64 65 | 62 75 67 3a 0a 09 24 28 |ALL)..de|bug:..$(|
|000044c0| 4d 41 4b 45 29 20 22 43 | 46 4c 41 47 53 3d 2d 44 |MAKE) "C|FLAGS=-D|
|000044d0| 44 45 42 55 47 3d 31 20 | 2d 67 20 24 28 43 46 4c |DEBUG=1 |-g $(CFL|
|000044e0| 41 47 53 29 22 20 63 6c | 65 61 6e 20 61 6c 6c 0a |AGS)" cl|ean all.|
|000044f0| 0a 6c 69 62 72 61 74 2e | 61 3a 20 24 28 4f 42 4a |.librat.|a: $(OBJ|
|00004500| 53 29 0a 09 61 72 20 72 | 76 20 6c 69 62 72 61 74 |S)..ar r|v librat|
|00004510| 2e 61 20 24 28 4f 42 4a | 53 29 0a 09 72 61 6e 6c |.a $(OBJ|S)..ranl|
|00004520| 69 62 20 6c 69 62 72 61 | 74 2e 61 0a 0a 64 65 70 |ib libra|t.a..dep|
|00004530| 65 6e 64 3a 20 41 4c 57 | 41 59 53 0a 09 72 6d 20 |end: ALW|AYS..rm |
|00004540| 2d 66 20 2e 64 65 70 65 | 6e 64 0a 09 66 6f 72 20 |-f .depe|nd..for |
|00004550| 64 20 69 6e 20 24 28 53 | 52 43 53 29 3b 20 64 6f |d in $(S|RCS); do|
|00004560| 20 24 28 43 43 29 20 24 | 28 43 46 4c 41 47 53 29 | $(CC) $|(CFLAGS)|
|00004570| 20 2d 4d 20 24 24 64 3b | 20 64 6f 6e 65 20 3e 3e | -M $$d;| done >>|
|00004580| 2e 64 65 70 65 6e 64 0a | 0a 63 6c 65 61 6e 3a 0a |.depend.|.clean:.|
|00004590| 09 72 6d 20 2d 72 66 20 | 2a 2e 61 20 2a 2e 6f 20 |.rm -rf |*.a *.o |
|000045a0| 0a 0a 69 6e 63 6c 75 64 | 65 73 3a 0a 09 63 70 20 |..includ|es:..cp |
|000045b0| 69 63 6f 6d 70 61 74 2e | 68 20 72 61 74 6c 69 62 |icompat.|h ratlib|
|000045c0| 2e 68 20 64 6b 64 74 72 | 65 65 2e 68 20 73 70 6c |.h dkdtr|ee.h spl|
|000045d0| 61 79 6c 69 62 2e 68 20 | 2e 2e 2f 2e 2e 2f 69 6e |aylib.h |../../in|
|000045e0| 63 6c 75 64 65 73 0a 0a | 74 65 73 74 74 72 65 65 |cludes..|testtree|
|000045f0| 73 3a 20 74 65 73 74 74 | 72 65 65 73 2e 6f 20 6c |s: testt|rees.o l|
|00004600| 69 62 72 61 74 2e 61 0a | 09 24 28 43 43 29 20 2d |ibrat.a.|.$(CC) -|
|00004610| 6f 20 24 40 20 24 40 2e | 6f 20 6c 69 62 72 61 74 |o $@ $@.|o librat|
|00004620| 2e 61 20 24 28 4c 49 42 | 53 29 09 0a 23 09 70 75 |.a $(LIB|S)..#.pu|
|00004630| 72 69 66 79 20 24 28 50 | 55 52 45 4f 50 54 53 29 |rify $(P|UREOPTS)|
|00004640| 20 24 28 43 43 29 20 2d | 6f 20 24 40 20 24 40 2e | $(CC) -|o $@ $@.|
|00004650| 6f 20 6c 69 62 72 61 74 | 2e 61 20 24 28 4c 49 42 |o librat|.a $(LIB|
|00004660| 53 29 0a 09 0a 41 4c 57 | 41 59 53 3a 0a 0a 69 63 |S)...ALW|AYS:..ic|
|00004670| 75 6c 61 72 20 6c 6f 63 | 61 74 69 6f 6e 2e 0a 49 |ular loc|ation..I|
|00004680| 66 20 74 68 65 72 65 20 | 69 73 20 6e 6f 20 65 78 |f there |is no ex|
|00004690| 61 63 74 20 6d 61 74 63 | 68 2c 20 68 6f 77 65 76 |act matc|h, howev|
|000046a0| 65 72 2c 20 61 20 22 63 | 6c 6f 73 65 22 20 72 65 |er, a "c|lose" re|
|000046b0| 67 69 6f 6e 20 69 73 20 | 72 65 74 75 72 6e 65 64 |gion is |returned|
|000046c0| 2e 20 20 49 6e 20 74 68 | 69 73 0a 73 65 6e 73 65 |.  In th|is.sense|
|000046d0| 2c 20 63 6c 6f 73 65 20 | 69 73 20 6d 65 61 73 75 |, close |is measu|
|000046e0| 72 65 64 20 62 6f 74 68 | 20 69 6e 20 63 65 6e 74 |red both| in cent|
|000046f0| 65 72 20 70 6f 69 6e 74 | 20 6c 6f 63 61 74 69 6f |er point| locatio|
|00004700| 6e 20 61 6e 64 20 69 6e | 20 72 65 63 74 61 6e 67 |n and in| rectang|
|00004710| 6c 65 0a 77 69 64 74 68 | 20 61 6e 64 20 68 65 69 |le.width| and hei|
|00004720| 67 68 74 2e 0a 41 73 20 | 64 65 73 63 72 69 62 65 |ght..As |describe|
|00004730| 64 20 69 6e 0a 2e 42 52 | 20 52 41 54 69 6e 74 72 |d in..BR| RATintr|
|00004740| 6f 20 28 33 29 2c 0a 72 | 65 63 74 61 6e 67 6c 65 |o (3),.r|ectangle|
|00004750| 73 20 61 72 65 20 64 65 | 66 69 6e 65 64 20 62 79 |s are de|fined by|
|00004760| 0a 2e 42 20 28 78 2c 79 | 2c 77 2c 68 29 2c 0a 77 |..B (x,y|,w,h),.w|
|00004770| 68 65 72 65 0a 2e 42 20 | 28 78 2c 79 29 0a 61 72 |here..B |(x,y).ar|
|00004780| 65 20 74 68 65 20 63 65 | 6e 74 65 72 20 6f 66 20 |e the ce|nter of |
|00004790| 74 68 65 20 72 65 63 74 | 61 6e 67 6c 65 20 61 6e |the rect|angle an|
|000047a0| 64 0a 2e 42 20 28 77 2c | 68 29 0a 61 72 65 20 74 |d..B (w,|h).are t|
|000047b0| 68 65 20 64 69 73 74 61 | 6e 63 65 73 20 66 72 6f |he dista|nces fro|
|000047c0| 6d 20 74 68 65 20 63 65 | 6e 74 65 72 20 74 6f 20 |m the ce|nter to |
|000047d0| 61 6e 20 65 64 67 65 2e | 20 20 28 53 69 6d 69 6c |an edge.|  (Simil|
|000047e0| 61 72 20 69 6e 20 6e 61 | 74 75 72 65 20 74 6f 20 |ar in na|ture to |
|000047f0| 74 68 65 20 63 65 6e 74 | 65 72 0a 61 6e 64 20 72 |the cent|er.and r|
|00004800| 72 61 74 6c 69 62 2f 73 | 72 63 2f 64 6b 64 74 72 |ratlib/s|rc/dkdtr|
|00004810| 65 65 2e 63 00 00 00 00 | 00 00 00 00 00 00 00 00 |ee.c....|........|
|00004820| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004830| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004840| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004850| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004860| 00 00 00 00 30 30 30 36 | 34 34 20 00 30 30 37 32 |....0006|44 .0072|
|00004870| 30 37 20 00 30 30 30 30 | 35 34 20 00 30 30 30 30 |07 .0000|54 .0000|
|00004880| 30 31 30 33 36 32 35 20 | 30 36 31 37 30 33 30 37 |0103625 |06170307|
|00004890| 31 36 37 20 30 31 35 35 | 33 35 00 20 30 00 00 00 |167 0155|35. 0...|
|000048a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000048b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000048c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000048d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000048e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000048f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004900| 00 75 73 74 61 72 00 30 | 30 6a 6d 63 63 00 00 00 |.ustar.0|0jmcc...|
|00004910| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004920| 00 00 00 00 00 00 00 00 | 00 70 63 76 69 73 69 6f |........|.pcvisio|
|00004930| 6e 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |n.......|........|
|00004940| 00 00 00 00 00 00 00 00 | 00 30 30 30 30 30 30 20 |........|.000000 |
|00004950| 00 30 30 30 30 30 30 20 | 00 00 00 00 00 00 00 00 |.000000 |........|
|00004960| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004970| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004980| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004990| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000049a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000049b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000049c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000049d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000049e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000049f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00004a00| 2f 2a 0a 20 2a 2a 20 20 | 20 20 20 43 6f 70 79 72 |/*. **  |   Copyr|
|00004a10| 69 67 68 74 20 28 43 29 | 20 31 39 39 35 20 20 52 |ight (C)| 1995  R|
|00004a20| 69 63 6b 20 52 6f 6d 65 | 72 6f 20 61 6e 64 20 43 |ick Rome|ro and C|
|00004a30| 61 72 6e 65 67 69 65 20 | 4d 65 6c 6c 6f 6e 20 55 |arnegie |Mellon U|
|00004a40| 6e 69 76 65 72 73 69 74 | 79 0a 20 2a 2a 0a 20 2a |niversit|y. **. *|
|00004a50| 2a 20 20 20 20 20 54 68 | 69 73 20 70 72 6f 67 72 |*     Th|is progr|
|00004a60| 61 6d 20 69 73 20 66 72 | 65 65 20 73 6f 66 74 77 |am is fr|ee softw|
|00004a70| 61 72 65 3b 20 79 6f 75 | 20 63 61 6e 20 72 65 64 |are; you| can red|
|00004a80| 69 73 74 72 69 62 75 74 | 65 20 69 74 20 61 6e 64 |istribut|e it and|
|00004a90| 2f 6f 72 20 6d 6f 64 69 | 66 79 0a 20 2a 2a 20 20 |/or modi|fy. **  |
|00004aa0| 20 20 20 69 74 20 75 6e | 64 65 72 20 74 68 65 20 |   it un|der the |
|00004ab0| 74 65 72 6d 73 20 6f 66 | 20 74 68 65 20 47 4e 55 |terms of| the GNU|
|00004ac0| 20 47 65 6e 65 72 61 6c | 20 50 75 62 6c 69 63 20 | General| Public |
|00004ad0| 4c 69 63 65 6e 73 65 20 | 61 73 20 70 75 62 6c 69 |License |as publi|
|00004ae0| 73 68 65 64 20 62 79 0a | 20 2a 2a 20 20 20 20 20 |shed by.| **     |
|00004af0| 74 68 65 20 46 72 65 65 | 20 53 6f 66 74 77 61 72 |the Free| Softwar|
|00004b00| 65 20 46 6f 75 6e 64 61 | 74 69 6f 6e 3b 20 65 69 |e Founda|tion; ei|
|00004b10| 74 68 65 72 20 76 65 72 | 73 69 6f 6e 20 31 2c 20 |ther ver|sion 1, |
|00004b20| 6f 72 20 28 61 74 20 79 | 6f 75 72 20 6f 70 74 69 |or (at y|our opti|
|00004b30| 6f 6e 29 0a 20 2a 2a 20 | 20 20 20 20 61 6e 79 20 |on). ** |    any |
|00004b40| 6c 61 74 65 72 20 76 65 | 72 73 69 6f 6e 2e 0a 20 |later ve|rsion.. |
|00004b50| 2a 2a 20 20 20 20 20 0a | 20 2a 2a 20 20 20 20 20 |**     .| **     |
|00004b60| 54 68 69 73 20 70 72 6f | 67 72 61 6d 20 69 73 20 |This pro|gram is |
|00004b70| 64 69 73 74 72 69 62 75 | 74 65 64 20 69 6e 20 74 |distribu|ted in t|
|00004b80| 68 65 20 68 6f 70 65 20 | 74 68 61 74 20 69 74 20 |he hope |that it |
|00004b90| 77 69 6c 6c 20 62 65 20 | 75 73 65 66 75 6c 2c 0a |will be |useful,.|
|00004ba0| 20 2a 2a 20 20 20 20 20 | 62 75 74 20 57 49 54 48 | **     |but WITH|
|00004bb0| 4f 55 54 20 41 4e 59 20 | 57 41 52 52 41 4e 54 59 |OUT ANY |WARRANTY|
|00004bc0| 3b 20 77 69 74 68 6f 75 | 74 20 65 76 65 6e 20 74 |; withou|t even t|
|00004bd0| 68 65 20 69 6d 70 6c 69 | 65 64 20 77 61 72 72 61 |he impli|ed warra|
|00004be0| 6e 74 79 20 6f 66 0a 20 | 2a 2a 20 20 20 20 20 4d |nty of. |**     M|
|00004bf0| 45 52 43 48 41 4e 54 41 | 42 49 4c 49 54 59 20 6f |ERCHANTA|BILITY o|
|00004c00| 72 20 46 49 54 4e 45 53 | 53 20 46 4f 52 20 41 20 |r FITNES|S FOR A |
|00004c10| 50 41 52 54 49 43 55 4c | 41 52 20 50 55 52 50 4f |PARTICUL|AR PURPO|
|00004c20| 53 45 2e 20 20 53 65 65 | 20 74 68 65 0a 20 2a 2a |SE.  See| the. **|
|00004c30| 20 20 20 20 20 47 4e 55 | 20 47 65 6e 65 72 61 6c |     GNU| General|
|00004c40| 20 50 75 62 6c 69 63 20 | 4c 69 63 65 6e 73 65 20 | Public |License |
|00004c50| 66 6f 72 20 6d 6f 72 65 | 20 64 65 74 61 69 6c 73 |for more| details|
|00004c60| 2e 0a 20 2a 2a 20 20 20 | 20 20 0a 20 2a 2a 20 20 |.. **   |  . **  |
|00004c70| 20 20 20 59 6f 75 20 73 | 68 6f 75 6c 64 20 68 61 |   You s|hould ha|
|00004c80| 76 65 20 72 65 63 65 69 | 76 65 64 20 61 20 63 6f |ve recei|ved a co|
|00004c90| 70 79 20 6f 66 20 74 68 | 65 20 47 4e 55 20 47 65 |py of th|e GNU Ge|
|00004ca0| 6e 65 72 61 6c 20 50 75 | 62 6c 69 63 20 4c 69 63 |neral Pu|blic Lic|
|00004cb0| 65 6e 73 65 0a 20 2a 2a | 20 20 20 20 20 61 6c 6f |ense. **|     alo|
|00004cc0| 6e 67 20 77 69 74 68 20 | 74 68 69 73 20 70 72 6f |ng with |this pro|
|00004cd0| 67 72 61 6d 3b 20 69 66 | 20 6e 6f 74 2c 20 77 72 |gram; if| not, wr|
|00004ce0| 69 74 65 20 74 6f 20 74 | 68 65 20 46 72 65 65 20 |ite to t|he Free |
|00004cf0| 53 6f 66 74 77 61 72 65 | 0a 20 2a 2a 20 20 20 20 |Software|. **    |
|00004d00| 20 46 6f 75 6e 64 61 74 | 69 6f 6e 2c 20 49 6e 63 | Foundat|ion, Inc|
|00004d10| 2e 2c 20 36 37 35 20 4d | 61 73 73 20 41 76 65 2c |., 675 M|ass Ave,|
|00004d20| 20 43 61 6d 62 72 69 64 | 67 65 2c 20 4d 41 20 30 | Cambrid|ge, MA 0|
|00004d30| 32 31 33 39 2c 20 55 53 | 41 2e 0a 20 2a 2f 0a 0a |2139, US|A.. */..|
|00004d40| 23 69 6e 63 6c 75 64 65 | 20 3c 73 74 64 69 6f 2e |#include| <stdio.|
|00004d50| 68 3e 0a 23 69 6e 63 6c | 75 64 65 20 3c 73 74 64 |h>.#incl|ude <std|
|00004d60| 6c 69 62 2e 68 3e 0a 23 | 69 6e 63 6c 75 64 65 20 |lib.h>.#|include |
|00004d70| 3c 6d 61 74 68 2e 68 3e | 0a 23 69 6e 63 6c 75 64 |<math.h>|.#includ|
|00004d80| 65 20 3c 76 61 6c 75 65 | 73 2e 68 3e 0a 0a 23 69 |e <value|s.h>..#i|
|00004d90| 6e 63 6c 75 64 65 20 22 | 64 6b 64 74 72 65 65 2e |nclude "|dkdtree.|
|00004da0| 68 22 0a 0a 0a 23 64 65 | 66 69 6e 65 20 44 4b 44 |h"...#de|fine DKD|
|00004db0| 4c 45 41 46 5f 4d 41 4c | 4c 4f 43 5f 53 49 5a 45 |LEAF_MAL|LOC_SIZE|
|00004dc0| 20 31 30 30 0a 0a 73 74 | 61 74 69 63 20 44 4b 44 | 100..st|atic DKD|
|00004dd0| 4c 65 61 66 5f 70 20 44 | 4b 44 4c 65 61 66 46 72 |Leaf_p D|KDLeafFr|
|00004de0| 65 65 4c 69 73 74 20 3d | 20 4e 55 4c 4c 3b 0a 0a |eeList =| NULL;..|
|00004df0| 53 70 6c 61 79 4e 6f 64 | 65 5f 70 20 44 4b 44 46 |SplayNod|e_p DKDF|
|00004e00| 69 6e 64 4b 74 68 52 65 | 63 75 72 73 65 28 53 70 |indKthRe|curse(Sp|
|00004e10| 6c 61 79 4e 6f 64 65 5f | 70 2c 20 69 6e 74 2c 20 |layNode_|p, int, |
|00004e20| 69 6e 74 20 2a 29 3b 0a | 53 70 6c 61 79 4e 6f 64 |int *);.|SplayNod|
|00004e30| 65 5f 70 20 44 4b 44 46 | 69 6e 64 4d 65 64 69 61 |e_p DKDF|indMedia|
|00004e40| 6e 28 53 70 6c 61 79 54 | 72 65 65 5f 70 2c 20 69 |n(SplayT|ree_p, i|
|00004e50| 6e 74 29 3b 0a 76 6f 69 | 64 20 20 20 20 20 20 20 |nt);.voi|d       |
|00004e60| 20 44 4b 44 52 65 62 61 | 6c 61 6e 63 65 4c 6f 77 | DKDReba|lanceLow|
|00004e70| 65 72 4c 65 76 65 6c 73 | 28 44 4b 44 4e 6f 64 65 |erLevels|(DKDNode|
|00004e80| 5f 70 2c 20 44 4b 44 4e | 6f 64 65 5f 70 2c 20 69 |_p, DKDN|ode_p, i|
|00004e90| 6e 74 33 32 2c 20 69 6e | 74 33 32 29 3b 0a 76 6f |nt32, in|t32);.vo|
|00004ea0| 69 64 20 20 20 20 20 20 | 20 20 44 4b 44 52 65 62 |id      |  DKDReb|
|00004eb0| 75 69 6c 64 54 72 65 65 | 28 44 4b 44 54 72 65 65 |uildTree|(DKDTree|
|00004ec0| 5f 70 29 3b 0a 69 6e 74 | 20 20 20 20 20 20 20 20 |_p);.int|        |
|00004ed0| 20 44 4b 44 52 65 63 75 | 72 73 65 52 65 62 75 69 | DKDRecu|rseRebui|
|00004ee0| 6c 64 28 53 70 6c 61 79 | 54 72 65 65 5f 70 2c 20 |ld(Splay|Tree_p, |
|00004ef0| 53 70 6c 61 79 54 72 65 | 65 5f 70 2c 20 69 6e 74 |SplayTre|e_p, int|
|00004f00| 2c 20 69 6e 74 33 32 2c | 0a 09 09 09 20 20 20 20 |, int32,|....    |
|00004f10| 20 20 69 6e 74 33 32 2c | 20 69 6e 74 33 32 29 3b |  int32,| int32);|
|00004f20| 0a 76 6f 69 64 20 20 20 | 20 20 20 20 20 44 4b 44 |.void   |     DKD|
|00004f30| 52 65 63 75 72 73 65 43 | 6f 70 79 41 6e 64 46 72 |RecurseC|opyAndFr|
|00004f40| 65 65 45 6c 65 6d 65 6e | 74 73 28 53 70 6c 61 79 |eeElemen|ts(Splay|
|00004f50| 4e 6f 64 65 5f 70 2c 20 | 53 70 6c 61 79 54 72 65 |Node_p, |SplayTre|
|00004f60| 65 5f 70 29 3b 0a 76 6f | 69 64 20 20 20 20 20 20 |e_p);.vo|id      |
|00004f70| 20 20 44 4b 44 52 65 63 | 75 72 73 65 43 72 65 61 |  DKDRec|urseCrea|
|00004f80| 74 65 41 6e 64 46 72 65 | 65 28 53 70 6c 61 79 4e |teAndFre|e(SplayN|
|00004f90| 6f 64 65 5f 70 2c 20 53 | 70 6c 61 79 54 72 65 65 |ode_p, S|playTree|
|00004fa0| 5f 70 2c 20 69 6e 74 29 | 3b 0a 76 6f 69 64 20 20 |_p, int)|;.void  |
|00004fb0| 20 20 20 20 20 20 44 4b | 44 43 72 65 61 74 65 53 |      DK|DCreateS|
|00004fc0| 6f 72 74 54 72 65 65 41 | 6e 64 46 72 65 65 28 44 |ortTreeA|ndFree(D|
|00004fd0| 4b 44 54 72 65 65 5f 70 | 2c 20 53 70 6c 61 79 54 |KDTree_p|, SplayT|
|00004fe0| 72 65 65 5f 70 29 3b 0a | 76 6f 69 64 20 20 20 20 |ree_p);.|void    |
|00004ff0| 20 20 20 20 44 4b 44 43 | 6f 70 79 41 6e 64 46 72 |    DKDC|opyAndFr|
|00005000| 65 65 54 72 65 65 45 6c | 65 6d 65 6e 74 73 28 53 |eeTreeEl|ements(S|
|00005010| 70 6c 61 79 54 72 65 65 | 5f 70 2c 20 53 70 6c 61 |playTree|_p, Spla|
|00005020| 79 54 72 65 65 5f 70 29 | 3b 0a 53 70 6c 61 79 4e |yTree_p)|;.SplayN|
|00005030| 6f 64 65 5f 70 20 44 4b | 44 46 69 6e 64 4c 61 73 |ode_p DK|DFindLas|
|00005040| 74 4f 66 28 53 70 6c 61 | 79 54 72 65 65 5f 70 2c |tOf(Spla|yTree_p,|
|00005050| 20 53 70 6c 61 79 4e 6f | 64 65 5f 70 2c 20 53 70 | SplayNo|de_p, Sp|
|00005060| 6c 61 79 4e 6f 64 65 5f | 70 2c 20 69 6e 74 2c 20 |layNode_|p, int, |
|00005070| 69 6e 74 20 2a 29 3b 0a | 53 70 6c 61 79 4e 6f 64 |int *);.|SplayNod|
|00005080| 65 5f 70 20 44 4b 44 53 | 6b 69 70 52 65 70 65 61 |e_p DKDS|kipRepea|
|00005090| 74 73 28 53 70 6c 61 79 | 54 72 65 65 5f 70 2c 20 |ts(Splay|Tree_p, |
|000050a0| 53 70 6c 61 79 4e 6f 64 | 65 5f 70 2c 20 69 6e 74 |SplayNod|e_p, int|
|000050b0| 2c 20 69 6e 74 20 2a 29 | 3b 0a 76 6f 69 64 20 20 |, int *)|;.void  |
|000050c0| 20 20 20 20 20 20 44 4b | 44 52 65 63 75 72 73 65 |      DK|DRecurse|
|000050d0| 44 65 73 74 72 6f 79 28 | 53 70 6c 61 79 4e 6f 64 |Destroy(|SplayNod|
|000050e0| 65 5f 70 2c 20 69 6e 74 | 29 3b 0a 69 6e 74 20 20 |e_p, int|);.int  |
|000050f0| 20 20 20 20 20 20 20 64 | 6b 64 5f 63 6f 6d 70 61 |       d|kd_compa|
|00005100| 72 65 5f 6e 6f 64 65 73 | 28 76 6f 69 64 20 2a 6f |re_nodes|(void *o|
|00005110| 62 6a 31 2c 20 76 6f 69 | 64 20 2a 6f 62 6a 32 29 |bj1, voi|d *obj2)|
|00005120| 3b 0a 69 6e 74 20 20 20 | 20 20 20 20 20 20 64 6b |;.int   |      dk|
|00005130| 64 5f 63 6f 6d 70 61 72 | 65 5f 6c 65 61 76 65 73 |d_compar|e_leaves|
|00005140| 28 76 6f 69 64 20 2a 6f | 62 6a 31 2c 20 76 6f 69 |(void *o|bj1, voi|
|00005150| 64 20 2a 6f 62 6a 32 29 | 3b 0a 69 6e 74 20 20 20 |d *obj2)|;.int   |
|00005160| 20 20 20 20 20 20 64 6b | 64 5f 63 6f 6d 70 61 72 |      dk|d_compar|
|00005170| 65 5f 6c 65 61 76 65 73 | 31 28 76 6f 69 64 20 2a |e_leaves|1(void *|
|00005180| 6f 62 6a 31 2c 20 76 6f | 69 64 20 2a 6f 62 6a 32 |obj1, vo|id *obj2|
|00005190| 29 3b 0a 69 6e 74 20 20 | 20 20 20 20 20 20 20 64 |);.int  |       d|
|000051a0| 6b 64 5f 63 6f 6d 70 61 | 72 65 5f 6c 65 61 76 65 |kd_compa|re_leave|
|000051b0| 73 32 28 76 6f 69 64 20 | 2a 6f 62 6a 31 2c 20 76 |s2(void |*obj1, v|
|000051c0| 6f 69 64 20 2a 6f 62 6a | 32 29 3b 0a 69 6e 74 20 |oid *obj|2);.int |
|000051d0| 20 20 20 20 20 20 20 20 | 64 6b 64 5f 63 6f 6d 70 |        |dkd_comp|
|000051e0| 61 72 65 5f 6c 65 61 76 | 65 73 33 28 76 6f 69 64 |are_leav|es3(void|
|000051f0| 20 2a 6f 62 6a 31 2c 20 | 76 6f 69 64 20 2a 6f 62 | *obj1, |void *ob|
|00005200| 6a 32 29 3b 0a 0a 0a 23 | 69 66 64 65 66 20 44 45 |j2);...#|ifdef DE|
|00005210| 42 55 47 0a 69 6e 74 20 | 72 65 62 61 6c 61 6e 63 |BUG.int |rebalanc|
|00005220| 65 5f 63 6f 75 6e 74 73 | 20 3d 20 30 3b 0a 69 6e |e_counts| = 0;.in|
|00005230| 74 20 72 65 62 75 69 6c | 64 5f 63 6f 75 6e 74 73 |t rebuil|d_counts|
|00005240| 20 3d 20 30 3b 0a 69 6e | 74 20 69 6e 73 65 72 74 | = 0;.in|t insert|
|00005250| 73 20 3d 20 30 3b 0a 69 | 6e 74 20 64 65 6c 65 74 |s = 0;.i|nt delet|
|00005260| 65 73 20 3d 20 30 3b 0a | 23 65 6e 64 69 66 0a 0a |es = 0;.|#endif..|
|00005270| 0a 0a 69 6e 74 20 64 6b | 64 5f 63 6f 6d 70 61 72 |..int dk|d_compar|
|00005280| 65 5f 6e 6f 64 65 73 28 | 76 6f 69 64 20 2a 6f 62 |e_nodes(|void *ob|
|00005290| 6a 31 2c 20 76 6f 69 64 | 20 2a 6f 62 6a 32 29 20 |j1, void| *obj2) |
|000052a0| 7b 0a 20 20 0a 20 20 2f | 2a 20 43 68 65 63 6b 20 |{.  .  /|* Check |
|000052b0| 74 6f 20 73 65 65 20 69 | 66 20 65 69 74 68 65 72 |to see i|f either|
|000052c0| 20 69 73 20 61 20 70 6f | 69 6e 74 2c 20 61 6e 64 | is a po|int, and|
|000052d0| 20 6e 6f 74 20 61 20 72 | 61 6e 67 65 20 2a 2f 0a | not a r|ange */.|
|000052e0| 20 20 69 66 20 28 28 28 | 44 4b 44 4e 6f 64 65 5f |  if (((|DKDNode_|
|000052f0| 70 29 20 6f 62 6a 31 29 | 2d 3e 6c 65 66 74 20 3d |p) obj1)|->left =|
|00005300| 3d 20 28 28 44 4b 44 4e | 6f 64 65 5f 70 29 20 6f |= ((DKDN|ode_p) o|
|00005310| 62 6a 31 29 2d 3e 72 69 | 67 68 74 29 20 7b 0a 20 |bj1)->ri|ght) {. |
|00005320| 20 20 20 69 66 20 28 28 | 28 44 4b 44 4e 6f 64 65 |   if ((|(DKDNode|
|00005330| 5f 70 29 20 6f 62 6a 32 | 29 2d 3e 6c 65 66 74 20 |_p) obj2|)->left |
|00005340| 3c 3d 20 28 28 44 4b 44 | 4e 6f 64 65 5f 70 29 20 |<= ((DKD|Node_p) |
|00005350| 6f 62 6a 31 29 2d 3e 6c | 65 66 74 29 20 7b 0a 20 |obj1)->l|eft) {. |
|00005360| 20 20 20 20 20 69 66 20 | 28 28 28 44 4b 44 4e 6f |     if |(((DKDNo|
|00005370| 64 65 5f 70 29 20 6f 62 | 6a 32 29 2d 3e 72 69 67 |de_p) ob|j2)->rig|
|00005380| 68 74 20 3e 20 28 28 44 | 4b 44 4e 6f 64 65 5f 70 |ht > ((D|KDNode_p|
|00005390| 29 20 6f 62 6a 31 29 2d | 3e 6c 65 66 74 29 20 7b |) obj1)-|>left) {|
|000053a0| 0a 09 72 65 74 75 72 6e | 20 30 3b 0a 20 20 20 20 |..return| 0;.    |
|000053b0| 20 20 7d 20 65 6c 73 65 | 20 7b 0a 09 72 65 74 75 |  } else| {..retu|
|000053c0| 72 6e 20 31 3b 0a 20 20 | 20 20 20 20 7d 0a 20 20 |rn 1;.  |    }.  |
|000053d0| 20 20 7d 20 65 6c 73 65 | 20 7b 0a 20 20 20 20 20 |  } else| {.     |
|000053e0| 20 72 65 74 75 72 6e 20 | 2d 31 3b 0a 20 20 20 20 | return |-1;.    |
|000053f0| 7d 0a 20 20 7d 20 65 6c | 73 65 20 69 66 20 28 28 |}.  } el|se if ((|
|00005400| 28 44 4b 44 4e 6f 64 65 | 5f 70 29 20 6f 62 6a 32 |(DKDNode|_p) obj2|
|00005410| 29 2d 3e 6c 65 66 74 20 | 3d 3d 20 28 28 44 4b 44 |)->left |== ((DKD|
|00005420| 4e 6f 64 65 5f 70 29 20 | 6f 62 6a 32 29 2d 3e 72 |Node_p) |obj2)->r|
|00005430| 69 67 68 74 29 20 7b 0a | 20 20 20 20 69 66 20 28 |ight) {.|    if (|
|00005440| 28 28 44 4b 44 4e 6f 64 | 65 5f 70 29 20 6f 62 6a |((DKDNod|e_p) obj|
|00005450| 31 29 2d 3e 6c 65 66 74 | 20 3c 3d 20 28 28 44 4b |1)->left| <= ((DK|
|00005460| 44 4e 6f 64 65 5f 70 29 | 20 6f 62 6a 32 29 2d 3e |DNode_p)| obj2)->|
|00005470| 6c 65 66 74 29 20 7b 0a | 20 20 20 20 20 20 69 66 |left) {.|      if|
|00005480| 20 28 28 28 44 4b 44 4e | 6f 64 65 5f 70 29 20 6f | (((DKDN|ode_p) o|
|00005490| 62 6a 31 29 2d 3e 72 69 | 67 68 74 20 3e 20 28 28 |bj1)->ri|ght > ((|
|000054a0| 44 4b 44 4e 6f 64 65 5f | 70 29 20 6f 62 6a 32 29 |DKDNode_|p) obj2)|
|000054b0| 2d 3e 6c 65 66 74 29 20 | 7b 0a 09 72 65 74 75 72 |->left) |{..retur|
|000054c0| 6e 20 30 3b 0a 20 20 20 | 20 20 20 7d 20 65 6c 73 |n 0;.   |   } els|
|000054d0| 65 20 7b 0a 09 72 65 74 | 75 72 6e 20 2d 31 3b 0a |e {..ret|urn -1;.|
|000054e0| 20 20 20 20 20 20 7d 0a | 20 20 20 20 7d 20 65 6c |      }.|    } el|
|000054f0| 73 65 20 7b 0a 20 20 20 | 20 20 20 72 65 74 75 72 |se {.   |   retur|
|00005500| 6e 20 31 3b 0a 20 20 20 | 20 7d 0a 20 20 7d 20 65 |n 1;.   | }.  } e|
|00005510| 6c 73 65 20 7b 0a 20 20 | 20 20 2f 2a 20 57 65 27 |lse {.  |  /* We'|
|00005520| 72 65 20 63 6f 6d 70 61 | 72 69 6e 67 20 69 6e 74 |re compa|ring int|
|00005530| 65 72 76 61 6c 73 2c 20 | 77 68 69 63 68 20 73 68 |ervals, |which sh|
|00005540| 6f 75 6c 64 20 61 6c 6c | 20 62 65 20 6e 6f 6e 2d |ould all| be non-|
|00005550| 6f 76 65 72 6c 61 70 70 | 69 6e 67 2c 20 73 6f 20 |overlapp|ing, so |
|00005560| 74 68 69 73 0a 20 20 20 | 20 20 2a 20 69 73 20 61 |this.   |  * is a|
|00005570| 20 62 69 74 20 65 61 73 | 69 65 72 2e 0a 20 20 20 | bit eas|ier..   |
|00005580| 20 20 2a 2f 0a 20 20 20 | 20 72 65 74 75 72 6e 20 |  */.   | return |
|00005590| 28 28 28 28 44 4b 44 4e | 6f 64 65 5f 70 29 20 6f |((((DKDN|ode_p) o|
|000055a0| 62 6a 31 29 2d 3e 6c 65 | 66 74 20 3d 3d 20 28 28 |bj1)->le|ft == ((|
|000055b0| 44 4b 44 4e 6f 64 65 5f | 70 29 20 6f 62 6a 32 29 |DKDNode_|p) obj2)|
|000055c0| 2d 3e 6c 65 66 74 29 20 | 3f 20 30 20 3a 0a 09 20 |->left) |? 0 :.. |
|000055d0| 20 20 20 28 28 28 44 4b | 44 4e 6f 64 65 5f 70 29 |   (((DK|DNode_p)|
|000055e0| 20 6f 62 6a 31 29 2d 3e | 6c 65 66 74 20 3e 20 28 | obj1)->|left > (|
|000055f0| 28 44 4b 44 4e 6f 64 65 | 5f 70 29 20 6f 62 6a 32 |(DKDNode|_p) obj2|
|00005600| 29 2d 3e 6c 65 66 74 29 | 20 3f 20 31 20 3a 20 2d |)->left)| ? 1 : -|
|00005610| 31 29 3b 0a 20 20 7d 0a | 2f 2a 20 20 69 66 20 28 |1);.  }.|/*  if (|
|00005620| 28 28 44 4b 44 4e 6f 64 | 65 5f 70 29 20 6f 62 6a |((DKDNod|e_p) obj|
|00005630| 32 29 2d 3e 6c 65 66 74 | 20 3c 3d 20 28 28 44 4b |2)->left| <= ((DK|
|00005640| 44 4e 6f 64 65 5f 70 29 | 20 6f 62 6a 31 29 2d 3e |DNode_p)| obj1)->|
|00005650| 6c 65 66 74 29 20 7b 0a | 20 20 20 20 69 66 20 28 |left) {.|    if (|
|00005660| 28 28 44 4b 44 4e 6f 64 | 65 5f 70 29 20 6f 62 6a |((DKDNod|e_p) obj|
|00005670| 32 29 2d 3e 72 69 67 68 | 74 20 3e 20 28 28 44 4b |2)->righ|t > ((DK|
|00005680| 44 4e 6f 64 65 5f 70 29 | 20 6f 62 6a 31 29 2d 3e |DNode_p)| obj1)->|
|00005690| 6c 65 66 74 29 20 7b 0a | 20 20 20 20 20 20 72 65 |left) {.|      re|
|000056a0| 74 75 72 6e 20 30 3b 0a | 20 20 20 20 7d 20 65 6c |turn 0;.|    } el|
|000056b0| 73 65 20 7b 0a 20 20 20 | 20 20 20 72 65 74 75 72 |se {.   |   retur|
|000056c0| 6e 20 31 3b 0a 20 20 20 | 20 7d 0a 20 20 7d 20 65 |n 1;.   | }.  } e|
|000056d0| 6c 73 65 20 7b 0a 20 20 | 20 20 72 65 74 75 72 6e |lse {.  |  return|
|000056e0| 20 2d 31 3b 0a 20 20 7d | 0a 2a 2f 0a 0a 7d 0a 0a | -1;.  }|.*/..}..|
|000056f0| 69 6e 74 20 64 6b 64 5f | 63 6f 6d 70 61 72 65 5f |int dkd_|compare_|
|00005700| 6c 65 61 76 65 73 28 76 | 6f 69 64 20 2a 6f 62 6a |leaves(v|oid *obj|
|00005710| 31 2c 20 76 6f 69 64 20 | 2a 6f 62 6a 32 29 20 7b |1, void |*obj2) {|
|00005720| 0a 20 20 69 66 20 28 28 | 28 44 4b 44 4c 65 61 66 |.  if ((|(DKDLeaf|
|00005730| 5f 70 29 20 6f 62 6a 31 | 29 2d 3e 6c 6f 63 61 74 |_p) obj1|)->locat|
|00005740| 69 6f 6e 5b 30 5d 20 3d | 3d 0a 20 20 20 20 20 20 |ion[0] =|=.      |
|00005750| 28 28 44 4b 44 4c 65 61 | 66 5f 70 29 20 6f 62 6a |((DKDLea|f_p) obj|
|00005760| 32 29 2d 3e 6c 6f 63 61 | 74 69 6f 6e 5b 30 5d 29 |2)->loca|tion[0])|
|00005770| 20 7b 0a 20 20 20 20 69 | 66 20 28 28 28 44 4b 44 | {.    i|f (((DKD|
|00005780| 4c 65 61 66 5f 70 29 20 | 6f 62 6a 31 29 2d 3e 6c |Leaf_p) |obj1)->l|
|00005790| 6f 63 61 74 69 6f 6e 5b | 31 5d 20 3d 3d 0a 09 28 |ocation[|1] ==..(|
|000057a0| 28 44 4b 44 4c 65 61 66 | 5f 70 29 20 6f 62 6a 32 |(DKDLeaf|_p) obj2|
|000057b0| 29 2d 3e 6c 6f 63 61 74 | 69 6f 6e 5b 31 5d 29 20 |)->locat|ion[1]) |
|000057c0| 7b 0a 20 20 20 20 20 20 | 69 66 20 28 28 28 44 4b |{.      |if (((DK|
|000057d0| 44 4c 65 61 66 5f 70 29 | 20 6f 62 6a 31 29 2d 3e |DLeaf_p)| obj1)->|
|000057e0| 6c 6f 63 61 74 69 6f 6e | 5b 32 5d 20 3d 3d 0a 09 |location|[2] ==..|
|000057f0| 20 20 28 28 44 4b 44 4c | 65 61 66 5f 70 29 20 6f |  ((DKDL|eaf_p) o|
|00005800| 62 6a 32 29 2d 3e 6c 6f | 63 61 74 69 6f 6e 5b 32 |bj2)->lo|cation[2|
|00005810| 5d 29 20 7b 0a 09 72 65 | 74 75 72 6e 20 28 28 28 |]) {..re|turn (((|
|00005820| 28 44 4b 44 4c 65 61 66 | 5f 70 29 20 6f 62 6a 31 |(DKDLeaf|_p) obj1|
|00005830| 29 2d 3e 6c 6f 63 61 74 | 69 6f 6e 5b 33 5d 20 3d |)->locat|ion[3] =|
|00005840| 3d 0a 09 09 20 28 28 44 | 4b 44 4c 65 61 66 5f 70 |=... ((D|KDLeaf_p|
|00005850| 29 20 6f 62 6a 32 29 2d | 3e 6c 6f 63 61 74 69 6f |) obj2)-|>locatio|
|00005860| 6e 5b 33 5d 29 20 3f 20 | 30 20 3a 0a 09 09 28 28 |n[3]) ? |0 :...((|
|00005870| 28 28 44 4b 44 4c 65 61 | 66 5f 70 29 20 6f 62 6a |((DKDLea|f_p) obj|
|00005880| 31 29 2d 3e 6c 6f 63 61 | 74 69 6f 6e 5b 33 5d 20 |1)->loca|tion[3] |
|00005890| 3c 0a 09 09 20 20 28 28 | 44 4b 44 4c 65 61 66 5f |<...  ((|DKDLeaf_|
|000058a0| 70 29 20 6f 62 6a 32 29 | 2d 3e 6c 6f 63 61 74 69 |p) obj2)|->locati|
|000058b0| 6f 6e 5b 33 5d 29 20 3f | 20 2d 31 20 3a 20 31 29 |on[3]) ?| -1 : 1)|
|000058c0| 29 3b 0a 20 20 20 20 20 | 20 7d 20 65 6c 73 65 20 |);.     | } else |
|000058d0| 72 65 74 75 72 6e 20 28 | 28 28 28 44 4b 44 4c 65 |return (|(((DKDLe|
|000058e0| 61 66 5f 70 29 20 6f 62 | 6a 31 29 2d 3e 6c 6f 63 |af_p) ob|j1)->loc|
|000058f0| 61 74 69 6f 6e 5b 32 5d | 20 3c 0a 09 09 20 20 20 |ation[2]| <...   |
|00005900| 20 20 20 28 28 44 4b 44 | 4c 65 61 66 5f 70 29 20 |   ((DKD|Leaf_p) |
|00005910| 6f 62 6a 32 29 2d 3e 6c | 6f 63 61 74 69 6f 6e 5b |obj2)->l|ocation[|
|00005920| 32 5d 29 20 3f 20 2d 31 | 20 3a 20 31 29 3b 0a 20 |2]) ? -1| : 1);. |
|00005930| 20 20 20 7d 20 65 6c 73 | 65 20 72 65 74 75 72 6e |   } els|e return|
|00005940| 20 28 28 28 28 44 4b 44 | 4c 65 61 66 5f 70 29 20 | ((((DKD|Leaf_p) |
|00005950| 6f 62 6a 31 29 2d 3e 6c | 6f 63 61 74 69 6f 6e 5b |obj1)->l|ocation[|
|00005960| 31 5d 20 3c 0a 09 09 20 | 20 20 20 28 28 44 4b 44 |1] <... |   ((DKD|
|00005970| 4c 65 61 66 5f 70 29 20 | 6f 62 6a 32 29 2d 3e 6c |Leaf_p) |obj2)->l|
|00005980| 6f 63 61 74 69 6f 6e 5b | 31 5d 29 20 3f 20 2d 31 |ocation[|1]) ? -1|
|00005990| 20 3a 20 31 29 3b 0a 20 | 20 7d 20 65 6c 73 65 20 | : 1);. | } else |
|000059a0| 72 65 74 75 72 6e 20 28 | 28 28 28 44 4b 44 4c 65 |return (|(((DKDLe|
|000059b0| 61 66 5f 70 29 20 6f 62 | 6a 31 29 2d 3e 6c 6f 63 |af_p) ob|j1)->loc|
|000059c0| 61 74 69 6f 6e 5b 30 5d | 20 3c 0a 09 09 20 20 28 |ation[0]| <...  (|
|000059d0| 28 44 4b 44 4c 65 61 66 | 5f 70 29 20 6f 62 6a 32 |(DKDLeaf|_p) obj2|
|000059e0| 29 2d 3e 6c 6f 63 61 74 | 69 6f 6e 5b 30 5d 29 20 |)->locat|ion[0]) |
|000059f0| 3f 20 2d 31 20 3a 20 31 | 29 3b 0a 0a 7d 0a 0a 69 |? -1 : 1|);..}..i|
|00005a00| 6e 74 20 64 6b 64 5f 63 | 6f 6d 70 61 72 65 5f 6c |nt dkd_c|ompare_l|
|00005a10| 65 61 76 65 73 31 28 76 | 6f 69 64 20 2a 6f 62 6a |eaves1(v|oid *obj|
|00005a20| 31 2c 20 76 6f 69 64 20 | 2a 6f 62 6a 32 29 20 7b |1, void |*obj2) {|
|00005a30| 0a 20 20 69 66 20 28 28 | 28 44 4b 44 4c 65 61 66 |.  if ((|(DKDLeaf|
|00005a40| 5f 70 29 20 6f 62 6a 31 | 29 2d 3e 6c 6f 63 61 74 |_p) obj1|)->locat|
|00005a50| 69 6f 6e 5b 31 5d 20 3d | 3d 0a 20 20 20 20 20 20 |ion[1] =|=.      |
|00005a60| 28 28 44 4b 44 4c 65 61 | 66 5f 70 29 20 6f 62 6a |((DKDLea|f_p) obj|
|00005a70| 32 29 2d 3e 6c 6f 63 61 | 74 69 6f 6e 5b 31 5d 29 |2)->loca|tion[1])|
|00005a80| 20 7b 0a 20 20 20 20 69 | 66 20 28 28 28 44 4b 44 | {.    i|f (((DKD|
|00005a90| 4c 65 61 66 5f 70 29 20 | 6f 62 6a 31 29 2d 3e 6c |Leaf_p) |obj1)->l|
|00005aa0| 6f 63 61 74 69 6f 6e 5b | 32 5d 20 3d 3d 0a 09 20 |ocation[|2] ==.. |
|00005ab0| 28 28 44 4b 44 4c 65 61 | 66 5f 70 29 20 6f 62 6a |((DKDLea|f_p) obj|
|00005ac0| 32 29 2d 3e 6c 6f 63 61 | 74 69 6f 6e 5b 32 5d 29 |2)->loca|tion[2])|
|00005ad0| 20 7b 0a 20 20 20 20 20 | 20 72 65 74 75 72 6e 20 | {.     | return |
|00005ae0| 28 28 28 28 44 4b 44 4c | 65 61 66 5f 70 29 20 6f |((((DKDL|eaf_p) o|
|00005af0| 62 6a 31 29 2d 3e 6c 6f | 63 61 74 69 6f 6e 5b 33 |bj1)->lo|cation[3|
|00005b00| 5d 20 3d 3d 0a 09 20 20 | 20 20 20 20 20 28 28 44 |] ==..  |     ((D|
|00005b10| 4b 44 4c 65 61 66 5f 70 | 29 20 6f 62 6a 32 29 2d |KDLeaf_p|) obj2)-|
|00005b20| 3e 6c 6f 63 61 74 69 6f | 6e 5b 33 5d 29 20 3f 20 |>locatio|n[3]) ? |
|00005b30| 30 20 3a 0a 09 20 20 20 | 20 20 20 28 28 28 28 44 |0 :..   |   ((((D|
|00005b40| 4b 44 4c 65 61 66 5f 70 | 29 20 6f 62 6a 31 29 2d |KDLeaf_p|) obj1)-|
|00005b50| 3e 6c 6f 63 61 74 69 6f | 6e 5b 33 5d 20 3c 0a 09 |>locatio|n[3] <..|
|00005b60| 09 28 28 44 4b 44 4c 65 | 61 66 5f 70 29 20 6f 62 |.((DKDLe|af_p) ob|
|00005b70| 6a 32 29 2d 3e 6c 6f 63 | 61 74 69 6f 6e 5b 33 5d |j2)->loc|ation[3]|
|00005b80| 29 20 3f 20 2d 31 20 3a | 20 31 29 29 3b 0a 20 20 |) ? -1 :| 1));.  |
|00005b90| 20 20 7d 20 65 6c 73 65 | 20 72 65 74 75 72 6e 20 |  } else| return |
|00005ba0| 28 28 28 28 44 4b 44 4c | 65 61 66 5f 70 29 20 6f |((((DKDL|eaf_p) o|
|00005bb0| 62 6a 31 29 2d 3e 6c 6f | 63 61 74 69 6f 6e 5b 32 |bj1)->lo|cation[2|
|00005bc0| 5d 20 3c 0a 09 09 20 20 | 20 20 28 28 44 4b 44 4c |] <...  |  ((DKDL|
|00005bd0| 65 61 66 5f 70 29 20 6f | 62 6a 32 29 2d 3e 6c 6f |eaf_p) o|bj2)->lo|
|00005be0| 63 61 74 69 6f 6e 5b 32 | 5d 29 20 3f 20 2d 31 20 |cation[2|]) ? -1 |
|00005bf0| 3a 20 31 29 3b 0a 20 20 | 7d 20 65 6c 73 65 20 72 |: 1);.  |} else r|
|00005c00| 65 74 75 72 6e 20 28 28 | 28 28 44 4b 44 4c 65 61 |eturn ((|((DKDLea|
|00005c10| 66 5f 70 29 20 6f 62 6a | 31 29 2d 3e 6c 6f 63 61 |f_p) obj|1)->loca|
|00005c20| 74 69 6f 6e 5b 31 5d 20 | 3c 0a 09 09 20 20 28 28 |tion[1] |<...  ((|
|00005c30| 44 4b 44 4c 65 61 66 5f | 70 29 20 6f 62 6a 32 29 |DKDLeaf_|p) obj2)|
|00005c40| 2d 3e 6c 6f 63 61 74 69 | 6f 6e 5b 31 5d 29 20 3f |->locati|on[1]) ?|
|00005c50| 20 2d 31 20 3a 20 31 29 | 3b 0a 7d 0a 0a 69 6e 74 | -1 : 1)|;.}..int|
|00005c60| 20 64 6b 64 5f 63 6f 6d | 70 61 72 65 5f 6c 65 61 | dkd_com|pare_lea|
|00005c70| 76 65 73 32 28 76 6f 69 | 64 20 2a 6f 62 6a 31 2c |ves2(voi|d *obj1,|
|00005c80| 20 76 6f 69 64 20 2a 6f | 62 6a 32 29 20 7b 0a 20 | void *o|bj2) {. |
|00005c90| 20 69 66 20 28 28 28 44 | 4b 44 4c 65 61 66 5f 70 | if (((D|KDLeaf_p|
|00005ca0| 29 20 6f 62 6a 31 29 2d | 3e 6c 6f 63 61 74 69 6f |) obj1)-|>locatio|
|00005cb0| 6e 5b 32 5d 20 3d 3d 0a | 20 20 20 20 20 20 28 28 |n[2] ==.|      ((|
|00005cc0| 44 4b 44 4c 65 61 66 5f | 70 29 20 6f 62 6a 32 29 |DKDLeaf_|p) obj2)|
|00005cd0| 2d 3e 6c 6f 63 61 74 69 | 6f 6e 5b 32 5d 29 20 7b |->locati|on[2]) {|
|00005ce0| 0a 20 20 20 20 72 65 74 | 75 72 6e 20 28 28 28 28 |.    ret|urn ((((|
|00005cf0| 44 4b 44 4c 65 61 66 5f | 70 29 20 6f 62 6a 31 29 |DKDLeaf_|p) obj1)|
|00005d00| 2d 3e 6c 6f 63 61 74 69 | 6f 6e 5b 33 5d 20 3d 3d |->locati|on[3] ==|
|00005d10| 0a 09 20 20 20 20 20 28 | 28 44 4b 44 4c 65 61 66 |..     (|(DKDLeaf|
|00005d20| 5f 70 29 20 6f 62 6a 32 | 29 2d 3e 6c 6f 63 61 74 |_p) obj2|)->locat|
|00005d30| 69 6f 6e 5b 33 5d 29 20 | 3f 20 30 20 3a 0a 09 20 |ion[3]) |? 0 :.. |
|00005d40| 20 20 20 28 28 28 28 44 | 4b 44 4c 65 61 66 5f 70 |   ((((D|KDLeaf_p|
|00005d50| 29 20 6f 62 6a 31 29 2d | 3e 6c 6f 63 61 74 69 6f |) obj1)-|>locatio|
|00005d60| 6e 5b 33 5d 20 3c 0a 09 | 20 20 20 20 20 20 28 28 |n[3] <..|      ((|
|00005d70| 44 4b 44 4c 65 61 66 5f | 70 29 20 6f 62 6a 32 29 |DKDLeaf_|p) obj2)|
|00005d80| 2d 3e 6c 6f 63 61 74 69 | 6f 6e 5b 33 5d 29 20 3f |->locati|on[3]) ?|
|00005d90| 20 2d 31 20 3a 20 31 29 | 29 3b 0a 20 20 7d 20 65 | -1 : 1)|);.  } e|
|00005da0| 6c 73 65 20 72 65 74 75 | 72 6e 20 28 28 28 28 44 |lse retu|rn ((((D|
|00005db0| 4b 44 4c 65 61 66 5f 70 | 29 20 6f 62 6a 31 29 2d |KDLeaf_p|) obj1)-|
|00005dc0| 3e 6c 6f 63 61 74 69 6f | 6e 5b 32 5d 20 3c 0a 09 |>locatio|n[2] <..|
|00005dd0| 09 20 20 28 28 44 4b 44 | 4c 65 61 66 5f 70 29 20 |.  ((DKD|Leaf_p) |
|00005de0| 6f 62 6a 32 29 2d 3e 6c | 6f 63 61 74 69 6f 6e 5b |obj2)->l|ocation[|
|00005df0| 32 5d 29 20 3f 20 2d 31 | 20 3a 20 31 29 3b 0a 7d |2]) ? -1| : 1);.}|
|00005e00| 0a 0a 69 6e 74 20 64 6b | 64 5f 63 6f 6d 70 61 72 |..int dk|d_compar|
|00005e10| 65 5f 6c 65 61 76 65 73 | 33 28 76 6f 69 64 20 2a |e_leaves|3(void *|
|00005e20| 6f 62 6a 31 2c 20 76 6f | 69 64 20 2a 6f 62 6a 32 |obj1, vo|id *obj2|
|00005e30| 29 20 7b 0a 20 20 72 65 | 74 75 72 6e 20 28 28 28 |) {.  re|turn (((|
|00005e40| 28 44 4b 44 4c 65 61 66 | 5f 70 29 20 6f 62 6a 31 |(DKDLeaf|_p) obj1|
|00005e50| 29 2d 3e 6c 6f 63 61 74 | 69 6f 6e 5b 33 5d 20 3d |)->locat|ion[3] =|
|00005e60| 3d 0a 09 20 20 20 28 28 | 44 4b 44 4c 65 61 66 5f |=..   ((|DKDLeaf_|
|00005e70| 70 29 20 6f 62 6a 32 29 | 2d 3e 6c 6f 63 61 74 69 |p) obj2)|->locati|
|00005e80| 6f 6e 5b 33 5d 29 20 3f | 20 30 20 3a 0a 09 20 20 |on[3]) ?| 0 :..  |
|00005e90| 28 28 28 28 44 4b 44 4c | 65 61 66 5f 70 29 20 6f |((((DKDL|eaf_p) o|
|00005ea0| 62 6a 31 29 2d 3e 6c 6f | 63 61 74 69 6f 6e 5b 33 |bj1)->lo|cation[3|
|00005eb0| 5d 20 3c 0a 09 20 20 20 | 20 28 28 44 4b 44 4c 65 |] <..   | ((DKDLe|
|00005ec0| 61 66 5f 70 29 20 6f 62 | 6a 32 29 2d 3e 6c 6f 63 |af_p) ob|j2)->loc|
|00005ed0| 61 74 69 6f 6e 5b 33 5d | 29 20 3f 20 2d 31 20 3a |ation[3]|) ? -1 :|
|00005ee0| 20 31 29 29 3b 0a 7d 0a | 0a 0a 74 79 70 65 64 65 | 1));.}.|..typede|
|00005ef0| 66 20 69 6e 74 20 28 2a | 63 6f 6d 70 61 72 65 5f |f int (*|compare_|
|00005f00| 66 75 6e 63 74 69 6f 6e | 29 28 76 6f 69 64 20 2a |function|)(void *|
|00005f10| 2c 20 76 6f 69 64 20 2a | 29 3b 0a 63 6f 6d 70 61 |, void *|);.compa|
|00005f20| 72 65 5f 66 75 6e 63 74 | 69 6f 6e 20 64 6b 64 5f |re_funct|ion dkd_|
|00005f30| 63 6f 6d 70 61 72 65 5f | 6c 65 61 76 65 73 5f 61 |compare_|leaves_a|
|00005f40| 72 72 61 79 5b 44 4b 44 | 5f 44 49 4d 45 4e 53 49 |rray[DKD|_DIMENSI|
|00005f50| 4f 4e 53 5d 20 3d 20 5c | 0a 7b 20 20 64 6b 64 5f |ONS] = \|.{  dkd_|
|00005f60| 63 6f 6d 70 61 72 65 5f | 6c 65 61 76 65 73 2c 20 |compare_|leaves, |
|00005f70| 64 6b 64 5f 63 6f 6d 70 | 61 72 65 5f 6c 65 61 76 |dkd_comp|are_leav|
|00005f80| 65 73 31 2c 20 64 6b 64 | 5f 63 6f 6d 70 61 72 65 |es1, dkd|_compare|
|00005f90| 5f 6c 65 61 76 65 73 32 | 2c 0a 20 20 20 20 20 64 |_leaves2|,.     d|
|00005fa0| 6b 64 5f 63 6f 6d 70 61 | 72 65 5f 6c 65 61 76 65 |kd_compa|re_leave|
|00005fb0| 73 33 20 20 7d 3b 0a 0a | 0a 0a 0a 23 69 66 64 65 |s3  };..|...#ifde|
|00005fc0| 66 20 44 45 42 55 47 0a | 69 6e 74 20 63 6f 75 6e |f DEBUG.|int coun|
|00005fd0| 74 5f 70 6f 69 6e 74 73 | 28 53 70 6c 61 79 4e 6f |t_points|(SplayNo|
|00005fe0| 64 65 5f 70 20 6e 6f 64 | 65 29 20 7b 0a 20 20 69 |de_p nod|e) {.  i|
|00005ff0| 6e 74 20 63 20 3d 20 30 | 3b 0a 0a 20 20 69 66 20 |nt c = 0|;..  if |
|00006000| 28 6e 6f 64 65 2d 3e 6c | 65 66 74 29 0a 20 20 20 |(node->l|eft).   |
|00006010| 20 63 20 3d 20 63 6f 75 | 6e 74 5f 70 6f 69 6e 74 | c = cou|nt_point|
|00006020| 73 28 6e 6f 64 65 2d 3e | 6c 65 66 74 29 3b 0a 0a |s(node->|left);..|
|00006030| 20 20 69 66 20 28 6e 6f | 64 65 2d 3e 72 69 67 68 |  if (no|de->righ|
|00006040| 74 29 0a 20 20 20 20 72 | 65 74 75 72 6e 20 28 31 |t).    r|eturn (1|
|00006050| 20 2b 20 63 20 2b 20 63 | 6f 75 6e 74 5f 70 6f 69 | + c + c|ount_poi|
|00006060| 6e 74 73 28 6e 6f 64 65 | 2d 3e 72 69 67 68 74 29 |nts(node|->right)|
|00006070| 29 3b 0a 0a 20 20 72 65 | 74 75 72 6e 20 28 31 2b |);..  re|turn (1+|
|00006080| 63 29 3b 0a 7d 0a 23 65 | 6e 64 69 66 0a 0a 0a 0a |c);.}.#e|ndif....|
|00006090| 44 4b 44 4c 65 61 66 5f | 70 20 44 4b 44 43 72 65 |DKDLeaf_|p DKDCre|
|000060a0| 61 74 65 4c 65 61 66 28 | 29 20 7b 0a 20 20 44 4b |ateLeaf(|) {.  DK|
|000060b0| 44 4c 65 61 66 5f 70 20 | 74 6d 70 3b 0a 0a 20 20 |DLeaf_p |tmp;..  |
|000060c0| 69 66 20 28 44 4b 44 4c | 65 61 66 46 72 65 65 4c |if (DKDL|eafFreeL|
|000060d0| 69 73 74 29 20 7b 0a 20 | 20 20 20 74 6d 70 20 3d |ist) {. |   tmp =|
|000060e0| 20 44 4b 44 4c 65 61 66 | 46 72 65 65 4c 69 73 74 | DKDLeaf|FreeList|
|000060f0| 3b 0a 20 20 20 20 44 4b | 44 4c 65 61 66 46 72 65 |;.    DK|DLeafFre|
|00006100| 65 4c 69 73 74 20 3d 20 | 28 44 4b 44 4c 65 61 66 |eList = |(DKDLeaf|
|00006110| 5f 70 29 20 74 6d 70 2d | 3e 6f 62 6a 5f 6c 69 73 |_p) tmp-|>obj_lis|
|00006120| 74 2e 6e 65 78 74 3b 0a | 20 20 7d 20 65 6c 73 65 |t.next;.|  } else|
|00006130| 20 7b 0a 20 20 20 20 69 | 6e 74 20 69 3b 0a 20 20 | {.    i|nt i;.  |
|00006140| 20 20 74 6d 70 20 3d 20 | 28 44 4b 44 4c 65 61 66 |  tmp = |(DKDLeaf|
|00006150| 5f 70 29 20 6d 61 6c 6c | 6f 63 28 73 69 7a 65 6f |_p) mall|oc(sizeo|
|00006160| 66 28 44 4b 44 4c 65 61 | 66 5f 74 29 20 2a 20 44 |f(DKDLea|f_t) * D|
|00006170| 4b 44 4c 45 41 46 5f 4d | 41 4c 4c 4f 43 5f 53 49 |KDLEAF_M|ALLOC_SI|
|00006180| 5a 45 29 3b 0a 20 20 20 | 20 74 6d 70 20 2b 3d 20 |ZE);.   | tmp += |
|00006190| 28 44 4b 44 4c 45 41 46 | 5f 4d 41 4c 4c 4f 43 5f |(DKDLEAF|_MALLOC_|
|000061a0| 53 49 5a 45 2d 31 29 3b | 0a 20 20 20 20 74 6d 70 |SIZE-1);|.    tmp|
|000061b0| 2d 3e 6f 62 6a 5f 6c 69 | 73 74 2e 6e 65 78 74 20 |->obj_li|st.next |
|000061c0| 3d 20 28 44 4b 44 4f 62 | 6a 4c 69 73 74 5f 70 29 |= (DKDOb|jList_p)|
|000061d0| 20 44 4b 44 4c 65 61 66 | 46 72 65 65 4c 69 73 74 | DKDLeaf|FreeList|
|000061e0| 3b 0a 20 20 20 20 74 6d | 70 2d 2d 3b 0a 20 20 20 |;.    tm|p--;.   |
|000061f0| 20 66 6f 72 20 28 69 3d | 44 4b 44 4c 45 41 46 5f | for (i=|DKDLEAF_|
|00006200| 4d 41 4c 4c 4f 43 5f 53 | 49 5a 45 2d 32 3b 20 69 |MALLOC_S|IZE-2; i|
|00006210| 3b 20 69 2d 2d 2c 20 74 | 6d 70 2d 2d 29 0a 20 20 |; i--, t|mp--).  |
|00006220| 20 20 20 20 74 6d 70 2d | 3e 6f 62 6a 5f 6c 69 73 |    tmp-|>obj_lis|
|00006230| 74 2e 6e 65 78 74 20 3d | 20 28 44 4b 44 4f 62 6a |t.next =| (DKDObj|
|00006240| 4c 69 73 74 5f 70 29 20 | 28 74 6d 70 2b 31 29 3b |List_p) |(tmp+1);|
|00006250| 0a 20 20 20 20 44 4b 44 | 4c 65 61 66 46 72 65 65 |.    DKD|LeafFree|
|00006260| 4c 69 73 74 20 3d 20 74 | 6d 70 2b 31 3b 0a 20 20 |List = t|mp+1;.  |
|00006270| 7d 0a 20 20 72 65 74 75 | 72 6e 20 74 6d 70 3b 0a |}.  retu|rn tmp;.|
|00006280| 7d 0a 0a 0a 76 6f 69 64 | 20 44 4b 44 46 72 65 65 |}...void| DKDFree|
|00006290| 4c 65 61 66 28 44 4b 44 | 4c 65 61 66 5f 70 20 6c |Leaf(DKD|Leaf_p l|
|000062a0| 65 61 66 29 20 7b 0a 20 | 20 69 66 20 28 6c 65 61 |eaf) {. | if (lea|
|000062b0| 66 29 20 7b 0a 20 20 20 | 20 6c 65 61 66 2d 3e 6f |f) {.   | leaf->o|
|000062c0| 62 6a 5f 6c 69 73 74 2e | 6e 65 78 74 20 3d 20 28 |bj_list.|next = (|
|000062d0| 44 4b 44 4f 62 6a 4c 69 | 73 74 5f 70 29 20 44 4b |DKDObjLi|st_p) DK|
|000062e0| 44 4c 65 61 66 46 72 65 | 65 4c 69 73 74 3b 0a 20 |DLeafFre|eList;. |
|000062f0| 20 20 20 44 4b 44 4c 65 | 61 66 46 72 65 65 4c 69 |   DKDLe|afFreeLi|
|00006300| 73 74 20 3d 20 6c 65 61 | 66 3b 0a 20 20 7d 0a 7d |st = lea|f;.  }.}|
|00006310| 0a 0a 0a 0a 76 6f 69 64 | 20 44 4b 44 52 65 63 75 |....void| DKDRecu|
|00006320| 72 73 65 44 65 73 74 72 | 6f 79 28 53 70 6c 61 79 |rseDestr|oy(Splay|
|00006330| 4e 6f 64 65 5f 70 20 73 | 6e 6f 64 65 2c 20 69 6e |Node_p s|node, in|
|00006340| 74 20 64 69 6d 65 6e 73 | 69 6f 6e 73 29 20 7b 0a |t dimens|ions) {.|
|00006350| 20 20 69 66 20 28 73 6e | 6f 64 65 3d 3d 4e 55 4c |  if (sn|ode==NUL|
|00006360| 4c 29 0a 20 20 20 20 72 | 65 74 75 72 6e 3b 0a 0a |L).    r|eturn;..|
|00006370| 20 20 69 66 20 28 64 69 | 6d 65 6e 73 69 6f 6e 73 |  if (di|mensions|
|00006380| 3e 30 29 20 7b 0a 20 20 | 20 20 0a 20 20 20 20 69 |>0) {.  |  .    i|
|00006390| 66 20 28 73 6e 6f 64 65 | 2d 3e 6c 65 66 74 29 20 |f (snode|->left) |
|000063a0| 7b 0a 20 20 20 20 20 20 | 44 4b 44 52 65 63 75 72 |{.      |DKDRecur|
|000063b0| 73 65 44 65 73 74 72 6f | 79 28 73 6e 6f 64 65 2d |seDestro|y(snode-|
|000063c0| 3e 6c 65 66 74 2c 20 64 | 69 6d 65 6e 73 69 6f 6e |>left, d|imension|
|000063d0| 73 29 3b 0a 20 20 20 20 | 7d 0a 0a 20 20 20 20 44 |s);.    |}..    D|
|000063e0| 4b 44 52 65 63 75 72 73 | 65 44 65 73 74 72 6f 79 |KDRecurs|eDestroy|
|000063f0| 28 28 28 44 4b 44 4e 6f | 64 65 5f 70 29 20 73 6e |(((DKDNo|de_p) sn|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.